C++ の動作確認をしてみた（７７０）

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題D (偶数メートル) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 036 解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://www.slideshare.net/chokudai/arc036
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. クエリ回答(解説通り).
    UnionFind uf(2 * N + 2);
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int w, x, y, z;
        scanf("%d %d %d %d", &w, &x, &y, &z);
        --x, --y;
        
        // 2-2. クエリ 1.
        if(w == 1){
            // 以下の頂点を用意して, UnionFind木 に 辺を追加していく.
            // 頂点(赤): 0 ～ N - 1, 頂点(青): N ～ 2 * N - 1.
            int rx = x;
            int ry = y;
            int bx = x + N;
            int by = y + N;
            
            // 道路が, 奇数メートル.
            if(z & 1){
                if(!uf.same(rx, by)) uf.unite(rx, by);
                if(!uf.same(bx, ry)) uf.unite(bx, ry);
            }
            
            // 道路が, 偶数メートル.
            if(!(z & 1)){
                if(!uf.same(rx, ry)) uf.unite(rx, ry);
                if(!uf.same(bx, by)) uf.unite(bx, by);
            }
        }
        
        // 2-3. クエリ 2.
        if(w == 2) printf("%s\n", uf.same(x, y) ? "YES" : "NO");
    }
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc036

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, Q;

scanf("%d %d", &N, &Q);

// 2. クエリ回答(解説通り).

UnionFind uf(2 * N + 2);

rep(i, Q){

// 2-1. クエリ入力情報.

int w, x, y, z;

scanf("%d %d %d %d", &w, &x, &y, &z);

--x, --y;

// 2-2. クエリ 1.

if(w == 1){

// 以下の頂点を用意して, UnionFind木に辺を追加していく.

// 頂点(赤): 0 ～ N - 1, 頂点(青): N ～ 2 * N - 1.

int rx = x;

int ry = y;

int bx = x + N;

int by = y + N;

// 道路が, 奇数メートル.

if(z & 1){

if(!uf.same(rx, by)) uf.unite(rx, by);

if(!uf.same(bx, ry)) uf.unite(bx, ry);

}

// 道路が, 偶数メートル.

if(!(z & 1)){

if(!uf.same(rx, ry)) uf.unite(rx, ry);

if(!uf.same(bx, by)) uf.unite(bx, by);

}

// 2-3. クエリ 2.

if(w == 2) printf("%s\n", uf.same(x, y) ? "YES" : "NO");

}

return 0;

}

[入力例]
5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

[出力例]
NO
YES
YES
YES
※AtCoderテストケースより

[入力例]
5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

[出力例]
NO
NO
NO
※AtCoderテストケースより

[入力例]
3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

[出力例]
YES
YES
※AtCoderテストケースより

[入力例]
7 15
1 1 3 5
2 1 3 1
1 3 4 1
2 1 4 1
1 6 4 2
1 5 4 3
1 7 6 5
2 4 7 1
2 3 7 1
2 1 6 1
1 2 3 7
2 5 7 1
2 5 2 1
1 4 1 3
2 5 2 1

[出力例]
NO
YES
NO
YES
YES
YES
NO
YES

[入力例]
11 24
1 1 11 5
2 1 11 1
1 1 2 3
2 2 11 1
1 3 2 5
1 3 7 8
1 8 3 1
2 8 1 1
1 4 5 6
1 4 10 2
1 9 5 3
1 4 11 7
1 6 7 2
2 6 1 1
2 11 10 1
2 8 6 1
1 3 4 5
2 11 10 1
1 1 11 2
2 1 11 1
2 2 6 1
1 6 11 9
2 2 6 1
2 8 6 1

[出力例]
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

5 9

1 1 2 3

1 1 3 2

1 3 5 5

2 1 5 1

2 2 5 1

1 2 4 4

1 1 4 6

2 1 5 1

2 3 5 1

[出力例]

YES

※AtCoderテストケースより

[入力例]

5 7

1 1 2 3

1 2 4 4

1 5 3 1

2 1 3 1

2 5 3 1

1 3 1 2

2 3 4 1

[出力例]

※AtCoderテストケースより

[入力例]

3 6

1 1 2 1

1 1 3 3

1 2 3 2

1 2 1 2

2 1 3 1

2 2 3 1

[出力例]

YES

※AtCoderテストケースより

[入力例]

7 15

1 1 3 5

2 1 3 1

1 3 4 1

2 1 4 1

1 6 4 2

1 5 4 3

1 7 6 5

2 4 7 1

2 3 7 1

2 1 6 1

1 2 3 7

2 5 7 1

2 5 2 1

1 4 1 3

2 5 2 1

[出力例]

YES

[入力例]

11 24

1 1 11 5

2 1 11 1

1 1 2 3

2 2 11 1

1 3 2 5

1 3 7 8

1 8 3 1

2 8 1 1

1 4 5 6

1 4 10 2

1 9 5 3

1 4 11 7

1 6 7 2

2 6 1 1

2 11 10 1

2 8 6 1

1 3 4 5

2 11 10 1

1 1 11 2

2 1 11 1

2 2 6 1

1 6 11 9

2 2 6 1

2 8 6 1

[出力例]

YES

■参照サイト
AtCoder Regular Contest 036
Union-Find木

C++の練習を兼ねて, AtCoder Regular Contest 036 の 問題D (偶数メートル) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題D (偶数メートル) を解いてみた.

コメントを残すコメントをキャンセル