AtCoder ABC #219 (サイシードプログラミングコンテスト2021) : G - Propagation

CodeforcesやCSAcademyで出そうな問題。
https://atcoder.jp/contests/abc219/tasks/abc219_g

問題

N頂点M辺のグラフが与えられる。
初期状態で、頂点iには番号iが書かれている。
以下のクエリを計Q個順次行うことを考える。

• 頂点vが指定されるので、vの隣接点の番号を、その時点のvのもので上書きする

全クエリを終えた後、各頂点に書かれた番号を求めよ。

解法

愚直に行うとO(NQ)かかりTLEする。
そこで、ある程度(√N)以上の次数を持つ点は、ちょっと特別扱いすることで伝播の処理を軽くする。

クエリの対象が、特別扱いでない点の場合、愚直に隣接点の番号を更新しよう。
特別扱いの場合、その時点の時刻(何回目のクエリか)とその時の番号を控えておこう。

以後、クエリ対象の点の処理を行うとき、直前で隣接する特別扱いの点のうち、自身の番号の最終更新時刻よりも後にクエリが実行されていた場合、自身の番号を上書きする。
このように、特別扱いの点の番号の伝搬を遅延させることで、負荷軽減を行える。

int N;
int M;
int C[202020];
int H[202020],done[202020],DC[202020];
int big[202020];
vector<int> B;
vector<int> E[202020];
vector<int> BE[202020];
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,N) C[i]=i,H[i]=-1,done[i]=-1;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		if(E[i].size()>500) {
			big[i]=1;
			B.push_back(i);
		}
	}
	FOR(i,N) FORR(e,E[i]) if(big[e]) BE[i].push_back(e);
	
	FOR(i,Q) {
		cin>>x;
		int cur=x-1;
		FORR(b,BE[cur]) if(done[b]>H[cur]) {
			H[cur]=done[b];
			C[cur]=DC[b];
		}
		
		done[cur]=H[cur]=i;
		DC[cur]=C[cur];
		if(!big[cur]) {
			FORR(e,E[cur]) {
				H[e]=i;
				C[e]=C[cur];
			}
		}
	}
	FOR(i,N) {
		int cur=i;
		FORR(b,BE[cur]) if(done[b]>H[cur]) {
			H[cur]=done[b];
			C[cur]=DC[b];
		}
		cout<<C[cur]t+1<<" ";
	}
	cout<<endl;
}

まとめ

途中setを使ったせいかTLE連発してしんどかった。