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

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

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

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

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

// 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--)
int ball[606060]; // ボール の (保存先)箱番号
int box[606060];  // 箱に入っている 最小 の ボール番号.

// 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(N + Q + 2);
    rep(i, N + Q + 2){
        uf.unite(i + 1, i + 1);
        ball[i + 1] = box[i + 1] = i + 1;
    }
    
    // 3. クエリ回答.
    int k = N;
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int t;
        scanf("%d", &t);
        
        // 3-2. クエリ 1.
        if(t == 1){
            int x, y;
            scanf("%d %d", &x, &y);
            
            // 箱 Y が 空である.
            if(!box[y]) continue;
            
            // 箱 X, Y が 空でない.
            if(box[x]){
                // 箱 X, Y の ボール番号(最小値)をマージ.
                uf.unite(box[x], box[y]);
                
                // 箱 X に保存したボール番号(最小値) を 保存.
                box[x] = uf.find(box[x]);
                
                // 上記ボール の (保存先)箱番号 を 保存.
                ball[box[x]] = x;
                ball[box[y]] = x;
                
                // 箱 Y を 空にする.
                box[y] = 0;
                
                // 次へ.
                continue;
            }
            
            // 箱 X が 空, 箱 Y が 空でない.
            // 箱 X に保存したボール番号(最小値) を 保存.
            box[x] = box[y];
            
            // 上記ボール の (保存先)箱番号 を 保存.
            ball[box[y]] = x;
            
            // 箱 Y を 空にする.
            box[y] = 0;
        }
        
        // 3-3. クエリ 2.
        if(t == 2){
            int x;
            scanf("%d", &x);
            
            // ボール数 を インクリメント.
            ++k;
            
            // ボール (k + 1) の (保存先)箱番号 を 保存.
            ball[k] = x;
            
            // 箱 X が 空でない.
            if(box[x]){
                // 箱 X に, ボール (k + 1) を 保存.
                // -> マージと解釈する.
                uf.unite(box[x], k);
                
                // 次へ.
                continue;
            }
            
            // 箱 X が 空である.
            box[x] = k;
        }
        
        // 3-4. クエリ 3.
        if(t == 3){
            int x;
            scanf("%d", &x);
            
            // ボール X を 保存している箱で, ボール番号の最小値は？
            int xMin = uf.find(x);
            
            // 出力.
            printf("%d\n", ball[xMin]);
        }
    }
    return 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

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

int ball[606060]; // ボールの (保存先)箱番号

int box[606060]; // 箱に入っている最小のボール番号.

// 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(N + Q + 2);

rep(i, N + Q + 2){

uf.unite(i + 1, i + 1);

ball[i + 1] = box[i + 1] = i + 1;

}

// 3. クエリ回答.

int k = N;

rep(i, Q){

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

int t;

scanf("%d", &t);

// 3-2. クエリ 1.

if(t == 1){

int x, y;

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

// 箱 Y が空である.

if(!box[y]) continue;

// 箱 X, Y が空でない.

if(box[x]){

// 箱 X, Y のボール番号(最小値)をマージ.

uf.unite(box[x], box[y]);

// 箱 X に保存したボール番号(最小値) を保存.

box[x] = uf.find(box[x]);

// 上記ボールの (保存先)箱番号を保存.

ball[box[x]] = x;

ball[box[y]] = x;

// 箱 Y を空にする.

box[y] = 0;

// 次へ.

continue;

}

// 箱 X が空, 箱 Y が空でない.

// 箱 X に保存したボール番号(最小値) を保存.

box[x] = box[y];

// 上記ボールの (保存先)箱番号を保存.

ball[box[y]] = x;

// 箱 Y を空にする.

box[y] = 0;

}

// 3-3. クエリ 2.

if(t == 2){

int x;

scanf("%d", &x);

// ボール数をインクリメント.

++k;

// ボール (k + 1) の (保存先)箱番号を保存.

ball[k] = x;

// 箱 X が空でない.

if(box[x]){

// 箱 X に, ボール (k + 1) を保存.

// -> マージと解釈する.

uf.unite(box[x], k);

// 次へ.

continue;

}

// 箱 X が空である.

box[x] = k;

}

// 3-4. クエリ 3.

if(t == 3){

int x;

scanf("%d", &x);

// ボール X を保存している箱で, ボール番号の最小値は？

int xMin = uf.find(x);

// 出力.

printf("%d\n", ball[xMin]);

}

return 0;

}

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

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

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

[出力例]
2
4
7
6

[入力例]
10 25
2 5
2 9
1 5 8
2 10
1 5 7
2 6
3 11
1 3 5
2 10
3 13
2 6
3 2
2 7
1 2 5
2 1
1 5 10
3 15
3 7
2 7
1 2 3
1 7 2
3 3
1 1 3
1 5 7
3 10

[出力例]
5
10
2
5
3
7
5

[入力例]
20 70
3 1
2 14
1 8 11
1 15 3
1 2 14
3 21
2 11
2 2
1 3 2
2 1
2 14
2 16
3 23
2 12
2 12
3 4
1 5 12
1 12 15
1 5 14
3 25
1 16 18
3 6
1 8 9
1 7 16
3 26
2 7
3 9
2 9
2 12
3 30
3 10
2 16
3 22
2 10
1 14 17
1 13 7
3 31
2 12
1 14 16
1 15 16
3 16
2 7
2 4
3 17
1 15 5
2 2
2 9
3 25
1 16 3
1 17 12
3 21
1 17 19
3 19
2 18
2 18
1 18 13
3 7
1 19 8
2 19
2 20
2 2
3 41
1 20 4
1 20 17
2 16 
2 15
3 3
1 8 11
2 17
2 4

[出力例]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

166

167

168

169

170

171

[入力例]

5 10

3 5

1 1 4

2 1

2 4

3 7

1 3 1

3 4

1 1 4

3 7

3 6

[出力例]

※AtCoderテストケースより

[入力例]

7 10

1 5 1

1 2 5

3 5

2 1

2 4

3 9

1 7 4

3 9

2 6

3 10

[出力例]

[入力例]

10 25

2 5

2 9

1 5 8

2 10

1 5 7

2 6

3 11

1 3 5

2 10

3 13

2 6

3 2

2 7

1 2 5

2 1

1 5 10

3 15

3 7

2 7

1 2 3

1 7 2

3 3

1 1 3

1 5 7

3 10

[出力例]

[入力例]

20 70

3 1

2 14

1 8 11

1 15 3

1 2 14

3 21

2 11

2 2

1 3 2

2 1

2 14

2 16

3 23

2 12

3 4

1 5 12

1 12 15

1 5 14

3 25

1 16 18

3 6

1 8 9

1 7 16

3 26

2 7

3 9

2 9

2 12

3 30

3 10

2 16

3 22

2 10

1 14 17

1 13 7

3 31

2 12

1 14 16

1 15 16

3 16

2 7

2 4

3 17

1 15 5

2 2

2 9

3 25

1 16 3

1 17 12

3 21

1 17 19

3 19

2 18

1 18 13

3 7

1 19 8

2 19

2 20

2 2

3 41

1 20 4

1 20 17

2 16

2 15

3 3

1 8 11

2 17

2 4

[出力例]

■参照サイト
トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)
Union-Find木

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

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

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

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