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

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

■感想.
1. 問題083は, 方針が見えなかったので, (問題083 (Colorful Graph) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 個人的には, 計算量削減のために, グラフを二つ作成するロジックが, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-01.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-02.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-03.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
int e[202020]; // {各頂点番号, 最後に, クエリによる処理が行われたクエリ番号}.
int q[202020]; // {クエリ番号, 色}.
int c[202020]; // {頂点番号, 色}.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N), F(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).
    int B = (int)sqrt(2 * M);
    rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);
    
    // 3. クエリ回答.
    int Q;
    q[0] = 1;
    rep(i, N) c[i] = 1;
    scanf("%d", &Q);
    rep(i, Q){
        // 3-1. クエリ情報.
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        
        // 3-2. 隣接する頂点数が大きい場合.
        int n = G[x].size();
        if(n > B){
            // 出力.
            printf("%d\n", c[x]);
            
            // 更新(隣接頂点).
            for(auto &u : F[x]) c[u] = y;
        }
        
        // 3-3. 隣接する頂点数が小さい場合.
        if(n <= B){
            // 最大値.
            int eMax = e[x];
            for(auto &u : G[x]) eMax = max(eMax, e[u]);
            
            // 出力.
            printf("%d\n", q[eMax]);
            
            // 更新(隣接頂点).
            for(auto &u : G[x]) c[u] = y;
        }
        
        // 3-4. 更新(自分自身).
        e[x] = i + 1;
        c[x] = y;
        
        // 3-5. クエリ保存.
        q[i + 1] = y;
    }
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-01.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-02.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-03.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int e[202020]; // {各頂点番号, 最後に, クエリによる処理が行われたクエリ番号}.

int q[202020]; // {クエリ番号, 色}.

int c[202020]; // {頂点番号, 色}.

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N), F(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).

int B = (int)sqrt(2 * M);

rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);

// 3. クエリ回答.

int Q;

q[0] = 1;

rep(i, N) c[i] = 1;

scanf("%d", &Q);

rep(i, Q){

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

int x, y;

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

x--;

// 3-2. 隣接する頂点数が大きい場合.

int n = G[x].size();

if(n > B){

// 出力.

printf("%d\n", c[x]);

// 更新(隣接頂点).

for(auto &u : F[x]) c[u] = y;

}

// 3-3. 隣接する頂点数が小さい場合.

if(n <= B){

// 最大値.

int eMax = e[x];

for(auto &u : G[x]) eMax = max(eMax, e[u]);

// 出力.

printf("%d\n", q[eMax]);

// 更新(隣接頂点).

for(auto &u : G[x]) c[u] = y;

}

// 3-4. 更新(自分自身).

e[x] = i + 1;

c[x] = y;

// 3-5. クエリ保存.

q[i + 1] = y;

}

return 0;

}

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

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

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

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

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

[出力例]
1
3
5
2
7

[入力例]
12 16
1 10
6 1
3 1
4 1
3 5
3 9
9 10
11 10
11 12
12 6
6 4
6 7
4 2
2 7
2 8
8 7
20
7 103
3 29
10 7
12 115
7 64
1 25
10 26
7 16
12 122
9 42
4 75
11 112
7 26
1 104
4 66
12 55
5 19
11 39
6 45
12 61

[出力例]
1
1
1
1
103
7
25
64
115
26
25
122
16
75
104
112
29
55
55
45

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

[入力例]

4 4

1 2

1 3

1 4

2 3

4 2

3 3

2 4

4 5

1 6

[出力例]

※AtCoderテストケースより

[入力例]

10 20

1 3

7 8

5 8

2 3

7 10

6 7

4 7

9 5

6 5

2 9

4 2

5 7

3 10

4 8

1 8

10 8

5 3

9 1

7 3

2 1

3 5

2 2

8 9

5 3

8 2

3 9

7 1

8 4

6 8

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

1 3

3 5

3 4

1 3

3 5

5 2

3 7

1 6

[出力例]

[入力例]

12 16

1 10

6 1

3 1

4 1

3 5

3 9

9 10

11 10

11 12

12 6

6 4

6 7

4 2

2 7

2 8

8 7

7 103

3 29

10 7

12 115

7 64

1 25

10 26

7 16

12 122

9 42

4 75

11 112

7 26

1 104

4 66

12 55

5 19

11 39

6 45

12 61

[出力例]

103

115

122

104

112

■参照サイト
083 – Colorful Graph
問題083 (Colorful Graph) 解説(その１)
問題083 (Colorful Graph) 解説(その２)
問題083 (Colorful Graph) 解説(その３)
問題083 (Colorful Graph) 解説(その４)

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

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

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

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