[ABC219] G - Propagation

[Q] https://atcoder.jp/contests/abc219/tasks/abc219_g

同じようなものを解いた気がして、記憶をたどる。
典型90の後半のほうだったかも。なんと開始2分でコードを掘り当てる。
https://atcoder.jp/contests/typical90/tasks/typical90_ce
https://atcoder.jp/contests/typical90/submissions/24059999

高鳴る胸を抑えて5分後に提出。ところがまさかのWA。何度チャレンジしても、怒涛のWA。こんなにゲタ履いてるのにチャレンジ失敗、大敗北、大惨事、哀れ。

コンテスト後も、7WA->5WA->4WA->3WA->2WA->1WAと見事にあらゆるバグを刻み40WAの末ゴール。
多分以下の2ケースでドジ踏んでいた。

Q1. border = 1 でテスト
6 5 3
1 2
2 3
3 4
4 5
5 6
4 2 3

A.
2 2 2 2 4 6 

Q2. border = 3 でテスト
6 5 4
1 2
1 3
1 4
1 5
5 6
1 6 5 2

A.
1 1 1 1 6 6

200000辺張った太陽みたいな頂点を200000回クエリしたら、200000*200000 の処理になってしまう。
省略するために、
1. いったん太陽頂点を処理スキップする。
2. 太陽に隣接している頂点をクエリするときに、太陽頂点から値を伝播させる。(lazy segtree と同じ感覚だと思った)
これでO(200000)がO(1)になった。

Q. 太陽頂点とみなす、結合数のボーダーをどうしよう？
A. 結構適当に決めちゃっていい。1000とか。
sqrt(M)+1に設定するのが最も賢いようだ。

Q. どう管理しよう？

A. 
入力例
6 5 4
1 2
1 3
1 4
1 5
5 6
1 6 5 2

を考える。

border = sqrt(6)+1 = 3要素数とする。

グラフGは以下。
G[1]={2,3,4,5} // 太陽
G[2]={1} // 太陽じゃない
G[3]={1}
G[4]={1}
G[5]={1,6}
G[6]={5}

・クエリ1( 1ターン目 )
頂点1は要素数4の頂点なので、cols[1..5]=1と更新しない。我慢。
自分のデータを更新するだけ。

cols[1]=1 // 今時点での色
qcols[1]=1 // 伝播させる色を保存
turn[1]=1 // 色変があった暫定ターン
qturn[1]=1 // 本来伝播させていたターンを保存

・クエリ6( 2ターン目 )
cols[6]=6が入っているが、本当に6なのか確認する。
もしG[6]が太陽と隣接しているなら、太陽から値を受け取る必要がある。

G[6]={5}だが、5は太陽じゃないので、cols[6]=6だとわかる。
G[6]={5}は要素数1で太陽じゃないので、

cols[6]=cols[5]=6 に変更。
turn[6]=turn[5]=2ターン目 とメモ。

・クエリ5( 3ターン目 )
cols[5]=6だが、本当に6か確認する。
G[5]={1,6}
1が太陽なので、色変があるか確認する。
turn[5]=2 > qturn[1]=1
もともとcols[5]=6のデータが最新で、qcols[1]=1は古いようだ。
cols[5]=6であっているとわかる。

G[5]={1,6}は要素数2なの太陽ではない。
cols[5]=cols[1]=cols[6]=6 に変更。
turn[5]=turn[1]=turn[6]=3ターン目 とメモ。

・クエリ2( 4ターン目 )
cols[2]=2が正しいか確かめる。
G[2]={1}
1は太陽なので、色変があるか確認する。
turn[2]=-1 < qturn[1]=1 なので、色変させる。
turn[2]=1に変更し、turn[2]=qcols[1]=1と変更を適用。

G[2]={1}
要素数1なので隣接を全部変更させる。
cols[2]=cols[1]=1
turn[2]=turn[1]=4ターン目 とメモ。

・解答
cols[1]=1が正しいか、隣接太陽を確かめる。隣接太陽がないから正しい。
cols[2]=1が正しいか、隣接太陽を確かめる。まあ正しい。
cols[3]=3が正しいか、隣接太陽を確かめる。turn[3]=-1 < qturn[1]=1なので色変 cols[3]=1
cols[4]=4が正しいか、隣接太陽を確かめる。turn[4]=-1 < qturn[1]=1なので色変 cols[4]=1
cols[5]=6が正しいか、隣接太陽を確かめる。まあ正しい。
cols[6]=6が正しいか、隣接太陽を確かめる。隣接太陽がないから正しい。

1 1 1 1 6 6
を得る。

Q. 色？
A. 典型83の問題文に則ってコードを構築してしまいました。
実装。

ll N, M, Q, border;
vector<ll> G[200010];
vector<ll> R[200010];
ll cols[200010];
ll turns[200010];
ll qcols[200010];
ll qturns[200010];

void ansout(){
 rep(i, N){
   for(auto v: R[i]) if (chmax(turns[i], qturns[v])) { // 本当にcols[x]が自分の色なのか。隣が大きいから変わってないだけか確認
      cols[i] = qcols[v];
   }
   cout << cols[i] ;
   if (i<N-1) cout << " ";
   else cout << endl;
 }
}

int main(){
 cincout();
 
 cin >> N >> M >> Q;
 border = sqrt(M)+1;
 rep(i, M){
   ll a, b;
   cin >> a >> b;
   --a, --b;
   G[a].push_back(b);
   G[b].push_back(a);
 }
 rep(i, N){
   cols[i] = i+1; // 自分の暫定色
   qcols[i] = i+1; // 伝播させる色
   turns[i] = -1; // 自分が更新したターン
   qturns[i] = -1; // 周囲に伝播させるターン
 }
 rep(i, N){
   for(auto v: G[i]) if ((ll)G[v].size() >= border) { // 大きいお友達だけ入れる
     R[i].push_back(v);
   }
 }
 
 rep(i, Q){
   ll x;
   cin >> x;
   --x;
   // 自分の色が正しいか確認
   for(auto v: R[x]) if (chmax(turns[x], qturns[v])) { // 本当にcols[x]が自分の色なのか。隣が大きいから変わってないだけか確認
      cols[x] = qcols[v]; // 自分よりも後に、大きい隣人の更新があったら色をもらう
   }
   turns[x] = i;
   if ((ll)G[x].size() < border){ // 自分が小さいなら伝播さす
     for (auto v: G[x]){
       cols[v] = cols[x];
       turns[v] = turns[x];
     }
   }
   else{ // 大きいなら伝播色をストック
     qturns[x] = i; 
     qcols[x] = cols[x];
   }
 }
 ansout();
}

​
https://atcoder.jp/contests/abc219/submissions/26009832