C++ の動作確認をしてみた（３３６）

C++の練習を兼ねて, AtCoder Beginner Contest 183 の問題F (Confluence) を解いてみた.

■感想.
1. 問題F は, Union-Find木のライブラリを, 上手く拡張することが出来たので, AC版に到達できたので良かったと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 183 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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--)
#define a first
#define b second
int c[202020];

// 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{
    vector<int> d;           // 生徒同士が, 同じ集団に属するか否かを管理.
    vector<map<int, int>> c; // 生徒を含む集団が属するクラス情報を管理.
    set<int> s;              // 合流済みの生徒であるか判定.
    UnionFind(int n = 0): d(n, -1), c(n) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int ox, int oy, int cx, int cy){
        int x = find(ox);
        int y = find(oy);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        
        // 生徒を含む集団が属するクラス情報を更新.
        if(s.count(ox) == 0) c[x][cx]++;
        if(s.count(oy) == 0) c[x][cy]++;
        for(auto &p : c[y]) c[x][p.a] += p.b;
        
        // 合流済みフラグ設定.
        s.insert(ox);
        s.insert(oy);
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
    int getClassSize(int ox, int cy){
        int x = find(ox);
        return c[x][cy];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%d", &c[i]);
    
    // 2. クエリ回答.
    UnionFind uf(N);
    rep(i, Q){
        // 2-1. クエリ種別.
        int f;
        scanf("%d", &f);
        
        // 2-2. f = 1 の 場合.
        if(f == 1){
            int a, b;
            scanf("%d %d", &a, &b);
            a--, b--;
            uf.unite(a, b, c[a], c[b]);
        }
        
        // 2-3. f = 2 の 場合.
        if(f == 2){
            int x, y;
            scanf("%d %d", &x, &y);
            x--;
            int ans = uf.getClassSize(x, y);
            if(uf.size(x) == 1 && c[x] == y) ans++; // 生徒 x のみの場合を考慮.
            printf("%d\n", ans);
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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--)

#define a first

#define b second

int c[202020];

// 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{

vector<int> d; // 生徒同士が, 同じ集団に属するか否かを管理.

vector<map<int, int>> c; // 生徒を含む集団が属するクラス情報を管理.

set<int> s; // 合流済みの生徒であるか判定.

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

int find(int x){

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

}

bool unite(int ox, int oy, int cx, int cy){

int x = find(ox);

int y = find(oy);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

// 生徒を含む集団が属するクラス情報を更新.

if(s.count(ox) == 0) c[x][cx]++;

if(s.count(oy) == 0) c[x][cy]++;

for(auto &p : c[y]) c[x][p.a] += p.b;

// 合流済みフラグ設定.

s.insert(ox);

s.insert(oy);

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

int getClassSize(int ox, int cy){

int x = find(ox);

return c[x][cy];

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

rep(i, N) scanf("%d", &c[i]);

// 2. クエリ回答.

UnionFind uf(N);

rep(i, Q){

// 2-1. クエリ種別.

int f;

scanf("%d", &f);

// 2-2. f = 1 の場合.

if(f == 1){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

uf.unite(a, b, c[a], c[b]);

}

// 2-3. f = 2 の場合.

if(f == 2){

int x, y;

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

x--;

int ans = uf.getClassSize(x, y);

if(uf.size(x) == 1 && c[x] == y) ans++; // 生徒 x のみの場合を考慮.

printf("%d\n", ans);

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
1
0
2
0
1
2

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

[出力例]
0
0
0
0
0
1
1
1
0
3
2
3
3
0
0
2
1
4
4
3
1
2
4
4
3
0
4
0

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

[入力例]

5 5

1 2 3 2 1

1 1 2

1 2 5

2 1 1

1 3 4

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4

2 2 2 2 2

1 1 2

1 1 3

1 2 3

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

12 9

1 2 3 1 2 3 1 2 3 1 2 3

1 1 2

1 3 4

1 5 6

1 7 8

2 2 1

1 9 10

2 5 6

1 4 8

2 6 1

[出力例]

※AtCoderテストケースより

[入力例]

5 15

1 2 3 3 2

1 2 1

1 3 1

1 5 2

1 3 2

2 5 3

1 5 1

2 4 2

2 3 2

1 3 5

2 4 2

2 1 1

1 4 3

1 2 3

1 3 1

2 2 3

[出力例]

[入力例]

10 60

3 5 2 2 2 5 4 5 3 2

2 5 4

2 9 1

1 10 8

2 1 1

1 1 2

1 6 8

1 1 4

1 1 7

1 5 4

1 1 8

2 1 1

1 2 8

1 1 6

2 7 1

1 2 4

2 5 4

2 1 3

1 8 6

2 9 3

1 2 9

2 3 5

2 6 5

2 5 3

2 8 2

1 2 8

1 6 8

2 2 5

2 7 1

1 5 2

1 9 3

1 5 7

2 3 1

1 8 2

1 6 5

2 8 3

1 4 3

1 3 4

1 6 7

1 5 3

2 3 4

1 5 9

1 5 3

1 9 5

2 3 2

1 7 3

1 5 8

2 2 2

2 4 5

2 8 4

2 10 3

2 2 2

1 8 7

2 6 5

2 4 1

1 1 10

1 9 10

2 6 2

1 3 5

2 2 1

[出力例]

■参照サイト
AtCoder Beginner Contest 183
Union-Find木

C++の練習を兼ねて, AtCoder Beginner Contest 183 の 問題F (Confluence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 183 の問題F (Confluence) を解いてみた.

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