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

C++の練習を兼ねて, AtCoder Beginner Contest 187 の問題E (Through Path) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できた.
2. 幅優先探索(応用版, 累積和を考慮)の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc187/editorial/487
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vp = vector<P>;
#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
#define a first
#define b second
LL c[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    vp E;
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
        E.pb({a, b});
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 累積和(いもす法)を考慮した拡張版.
    auto bfsEx = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, c[e] += c[u], q.push(e);
            }
        }
        return;
    };
    int d[N];
    memset(d, 0, sizeof(d));
    bfsEx(G, 0, d);
    
    // 3. クエリ実行.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 3-1. 入力情報.
        int t, e;
        LL x;
        scanf("%d %d %lld", &t, &e, &x);
        e--;
        int a = E[e].a, b = E[e].b;
        
        // 3-2. t が 1 の 場合.
        // -> 何もしない.
        if(t == 1){}
        
        // 3-3. t が 2 の 場合.
        // -> a, b の 入れ替え.
        if(t == 2) swap(a, b);
        
        // 3-4. 頂点 1 からの距離が, 頂点 a < 頂点 b の 場合.
        // 根 の 子孫 に, x を 加算, 頂点 b の 子孫 に -x を 加算.
        if(d[a] < d[b]) c[0] += x, c[b] -= x;
        
        // 3-5. 頂点 1 からの距離が, 頂点 a > 頂点 b の 場合.
        // 頂点 a の 子孫 に, x を 加算.
        if(d[a] > d[b]) c[a] += x;
    }
    
    // 4. いもす法.
    memset(d, 0, sizeof(d));
    bfsEx(G, 0, d);
    
    // 5. 出力.
    rep(i, N) printf("%lld\n", c[i]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc187/editorial/487

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vvi = vector<vi>;

using vp = vector<P>;

#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

#define a first

#define b second

LL c[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

vp E;

rep(i, N - 1){

int a, b;

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

a--;

b--;

G[a].pb(b);

G[b].pb(a);

E.pb({a, b});

}

// 2. 頂点 1 から各頂点までの距離を計算.

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

// -> 累積和(いもす法)を考慮した拡張版.

auto bfsEx = [&](vvi &G, int s, int* d){

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

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]){

// 2-5. 訪問済であれば, 処理をスキップ.

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, c[e] += c[u], q.push(e);

}

return;

};

int d[N];

memset(d, 0, sizeof(d));

bfsEx(G, 0, d);

// 3. クエリ実行.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 3-1. 入力情報.

int t, e;

LL x;

scanf("%d %d %lld", &t, &e, &x);

e--;

int a = E[e].a, b = E[e].b;

// 3-2. t が 1 の場合.

// -> 何もしない.

if(t == 1){}

// 3-3. t が 2 の場合.

// -> a, b の入れ替え.

if(t == 2) swap(a, b);

// 3-4. 頂点 1 からの距離が, 頂点 a < 頂点 b の場合.

// 根の子孫に, x を加算, 頂点 b の子孫に -x を加算.

if(d[a] < d[b]) c[0] += x, c[b] -= x;

// 3-5. 頂点 1 からの距離が, 頂点 a > 頂点 b の場合.

// 頂点 a の子孫に, x を加算.

if(d[a] > d[b]) c[a] += x;

}

// 4. いもす法.

memset(d, 0, sizeof(d));

bfsEx(G, 0, d);

// 5. 出力.

rep(i, N) printf("%lld\n", c[i]);

return 0;

}

[入力例]
5
1 2
2 3
2 4
4 5
4
1 1 1
1 4 10
2 1 100
2 2 1000

[出力例]
11
110
1110
110
100
※AtCoderテストケースより

[入力例]
7
2 1
2 3
4 2
4 5
6 1
3 7
7
2 2 1
1 3 2
2 2 4
1 6 8
1 3 16
2 4 32
2 1 64

[出力例]
72
8
13
26
58
72
5
※AtCoderテストケースより

[入力例]
11
2 1
1 3
3 4
5 2
1 6
1 7
5 8
3 9
3 10
11 4
10
2 6 688
1 10 856
1 8 680
1 8 182
2 2 452
2 4 183
2 6 518
1 3 612
2 6 339
2 3 206

[出力例]
1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559
※AtCoderテストケースより

[入力例]
18
11 8
8 12
8 1
14 6
13 6
6 1
7 1
2 1
10 4
4 3
3 1
18 9
17 9
9 4
5 3
16 5
15 5
25
1 11 95950457
1 12 78750024
2 11 12922034
2 8 120429028
1 2 47370617
2 10 22549348
1 15 1797911
1 13 16211917
2 17 50579919
2 7 3753850
2 9 8677729
2 5 85237273
2 15 60953358
2 17 118168799
1 13 55676844
2 3 63974106
1 15 12703883
1 17 8094936
2 16 93042842
1 14 4325050
2 15 77051263
1 2 74890719
1 3 57631477
1 13 10482590
2 2 117493185

[出力例]
839600885
719171857
922629308
900079960
799126481
839600885
835847035
833258256
904405010
891402231
833258256
828490105
754363612
839600885
638472699
706083639
986776361
983155034

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

[入力例]

1 2

2 3

2 4

4 5

1 1 1

1 4 10

2 1 100

2 2 1000

[出力例]

110

1110

110

100

※AtCoderテストケースより

[入力例]

2 1

2 3

4 2

4 5

6 1

3 7

2 2 1

1 3 2

2 2 4

1 6 8

1 3 16

2 4 32

2 1 64

[出力例]

※AtCoderテストケースより

[入力例]

2 1

1 3

3 4

5 2

1 6

1 7

5 8

3 9

3 10

11 4

2 6 688

1 10 856

1 8 680

1 8 182

2 2 452

2 4 183

2 6 518

1 3 612

2 6 339

2 3 206

[出力例]

1657

2109

1703

1474

1657

3202

1474

1247

2109

2559

※AtCoderテストケースより

[入力例]

11 8

8 12

8 1

14 6

13 6

6 1

7 1

2 1

10 4

4 3

3 1

18 9

17 9

9 4

5 3

16 5

15 5

1 11 95950457

1 12 78750024

2 11 12922034

2 8 120429028

1 2 47370617

2 10 22549348

1 15 1797911

1 13 16211917

2 17 50579919

2 7 3753850

2 9 8677729

2 5 85237273

2 15 60953358

2 17 118168799

1 13 55676844

2 3 63974106

1 15 12703883

1 17 8094936

2 16 93042842

1 14 4325050

2 15 77051263

1 2 74890719

1 3 57631477

1 13 10482590

2 2 117493185

[出力例]

839600885

719171857

922629308

900079960

799126481

839600885

835847035

833258256

904405010

891402231

833258256

828490105

754363612

839600885

638472699

706083639

986776361

983155034

■参照サイト
AtCoder Beginner Contest 187

C++の練習を兼ねて, AtCoder Beginner Contest 187 の 問題E (Through Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 187 の問題E (Through Path) を解いてみた.

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