C++ の動作確認をしてみた（５２４）

C++の練習を兼ねて, 競プロ典型 90 問の問題068 (Paired Information) を解いてみた.

■感想.
1. 問題068は, 方針が見えなかったので, (問題068 (Paired Information) 解説) を参考に実装したところ, AC版に到達出来た.
2. 実装に非常に苦労したものの, 個人的には, Ambiguous であるか否かの判定に, グラフの連結状況(Union-Find木)を考える部分が, 非常に面白いと感じた.
3. Union-Find木, 幅優先探索の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題068 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/068.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#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 pb push_back
const int MAX = 101010;
int t[MAX], x[MAX], y[MAX];
LL v0[MAX], v1[MAX];

// 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);
    vvi G(N);
    rep(i, Q){
        LL u;
        scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);
        x[i]--;
        y[i]--;
        if(t[i]) v1[i] = u;
        else     v0[x[i]] = u;
        
        // グラフ作成.
        if(!t[i]){
            G[x[i]].pb(y[i]);
            G[y[i]].pb(x[i]);
        }
    }
    
    // 2. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 連結成分番号を設定.
        c[s] = l;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]) if(e != s && !c[e]) c[e] = l, q.push(e);
        }
        return;
    };
    int b[N], c[N], idx = 0;
    rep(i, N) b[i] = c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 3. 二つのパターン作成.
    // 3-1. 0 を ベース に考える場合.
    LL a0[N];
    a0[0] = 0;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];
        else                 a0[i + 1] = 0;
    }
    
    // 3-2. 1 を ベース に考える場合.
    LL a1[N];
    a1[0] = 1;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];
        else                 a1[i + 1] = 1;
    }
    
    // 4. クエリ回答.
    UnionFind uf(N + 1);
    rep(i, Q){
        // 4-1. T が 0 の 場合.
        if(!t[i]) uf.unite(x[i], y[i]);
        
        // 4-2. T が 1 の 場合.
        if(t[i]){
            // 確定しない場合.
            if(!uf.same(x[i], y[i])) puts("Ambiguous");
            
            // 確定する場合.
            if(uf.same(x[i], y[i])){
                // 基準値 + 符号(対象) × 符号(基準) × 差分
                LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);
                
                // 出力.
                printf("%lld\n", ans);
            }
        }
    }
    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

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/068.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

#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 pb push_back

const int MAX = 101010;

int t[MAX], x[MAX], y[MAX];

LL v0[MAX], v1[MAX];

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

vvi G(N);

rep(i, Q){

LL u;

scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);

x[i]--;

y[i]--;

if(t[i]) v1[i] = u;

else v0[x[i]] = u;

// グラフ作成.

if(!t[i]){

G[x[i]].pb(y[i]);

G[y[i]].pb(x[i]);

}

// 2. グラフを連結成分に分解.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* c, int l){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 連結成分番号を設定.

c[s] = l;

// 2-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

// 2-5. 取り出した要素を処理.

for(auto &e : G[u]) if(e != s && !c[e]) c[e] = l, q.push(e);

}

return;

};

int b[N], c[N], idx = 0;

rep(i, N) b[i] = c[i] = 0;

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 3. 二つのパターン作成.

// 3-1. 0 をベースに考える場合.

LL a0[N];

a0[0] = 0;

rep(i, N - 1){

if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];

else a0[i + 1] = 0;

}

// 3-2. 1 をベースに考える場合.

LL a1[N];

a1[0] = 1;

rep(i, N - 1){

if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];

else a1[i + 1] = 1;

}

// 4. クエリ回答.

UnionFind uf(N + 1);

rep(i, Q){

// 4-1. T が 0 の場合.

if(!t[i]) uf.unite(x[i], y[i]);

// 4-2. T が 1 の場合.

if(t[i]){

// 確定しない場合.

if(!uf.same(x[i], y[i])) puts("Ambiguous");

// 確定する場合.

if(uf.same(x[i], y[i])){

// 基準値 + 符号(対象) × 符号(基準) × 差分

LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);

// 出力.

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

}

return 0;

}

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

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

[入力例]
15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

[出力例]
8
33
33
33
68
33
144
93
8
108
118
※AtCoderテストケースより

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

[出力例]
5
Ambiguous
Ambiguous
-2
11
-1
1
Ambiguous

[入力例]
15
25
0 1 2 2
1 1 2 5
1 1 3 7
0 2 3 7
1 3 1 5
1 5 3 2
0 4 5 6
1 4 5 3
0 6 7 4
0 7 8 8
1 6 8 7
1 7 8 5
1 7 6 2
0 9 10 10
1 9 6 5
1 10 9 3
0 11 12 3
0 12 13 12
1 12 11 5
1 12 13 5
1 13 11 16
0 14 15 11
1 15 10 8
1 14 4 15
1 1 3 10

[出力例]
-3
Ambiguous
0
Ambiguous
3
11
3
2
Ambiguous
7
-2
7
7
Ambiguous
Ambiguous
15

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

[入力例]

0 1 2 3

1 1 2 1

1 3 4 5

0 3 4 6

1 3 4 5

0 2 3 6

1 3 1 5

[出力例]

Ambiguous

※AtCoderテストケースより

[入力例]

0 11 12 41

0 1 2 159

0 14 15 121

0 4 5 245

0 12 13 157

0 9 10 176

0 6 7 170

0 2 3 123

0 7 8 167

0 3 4 159

1 12 11 33

0 10 11 116

0 8 9 161

1 9 12 68

1 12 12 33

1 7 12 74

0 5 6 290

1 8 9 93

0 13 14 127

1 10 12 108

1 14 1 3

1 13 8 124

1 12 11 33

1 12 10 33

1 5 15 194

[出力例]

144

108

118

※AtCoderテストケースより

[入力例]

0 1 2 5

1 1 2 0

1 3 2 7

0 3 4 5

1 3 5 8

1 4 3 7

0 4 5 6

1 5 3 12

1 4 3 6

0 6 7 9

1 6 7 8

1 7 5 3

[出力例]

Ambiguous

-2

-1

Ambiguous

[入力例]

0 1 2 2

1 1 2 5

1 1 3 7

0 2 3 7

1 3 1 5

1 5 3 2

0 4 5 6

1 4 5 3

0 6 7 4

0 7 8 8

1 6 8 7

1 7 8 5

1 7 6 2

0 9 10 10

1 9 6 5

1 10 9 3

0 11 12 3

0 12 13 12

1 12 11 5

1 12 13 5

1 13 11 16

0 14 15 11

1 15 10 8

1 14 4 15

1 1 3 10

[出力例]

-3

Ambiguous

-2

Ambiguous

■参照サイト
068 – Paired Information
問題068 (Paired Information) 解説
 Union-Find木

C++の練習を兼ねて, 競プロ典型 90 問 の 問題068 (Paired Information) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題068 (Paired Information) を解いてみた.

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