Codeforces #561 Div2 F. Vicky's Delivery Service

割とゴリ押し。
https://codeforces.com/contest/1166/problem/F

問題

無向グラフにおいて、各辺に色が付けられている。
あるパスが虹色であるとは、始点から見て２本ずつ同じ色の辺を辿っていることを示す。
ただしパス長が奇数の場合、最後の辺は何色でもよい。
また、同じ辺・点を複数回通ってもよい。

以下のクエリに順次答えよ。

• 指定された頂点間に指定された辺を張る。
• 始点Sと終点Tが指定されるので、虹色のパスが存在するか判定する。

解法

同じ色の２本の辺でつながれた頂点は互いに任意に移動できる。
よってまずこれらをUnion-Findで連結させよう。

今頂点U-V間に色Cの辺を追加したとする。
その場合、Uに色Cでつながる点とVを連結させ、逆にVに色Cでつながる点とUを連結させよう。

次に判定クエリである。
偶数長の虹色パスがあるかどうかは、このUnion-Findで辿るだけである。
そうでない場合、Tの隣接点のうち、Sと偶数長の虹色パスを持つ、すなわち連結するものがあるか判定しよう。

ただしTの頂点数が多い場合、Tを終点とする判定クエリが多いとTLEする。
そこで平方分割の要領で、隣接点が多い頂点については、別途個別にTと隣接点をあらかじめ連結させた状態のUnion-Find構造を作り、以後辺追加クエリの時に上記同様に処理しておこう。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<105050> uf[205];

int N,M,C,Q;
map<int,int> PC[101010];
string T[101010];
int num[101010],X[101010],Y[101010],Z[101010],U[101010],V[101010],R[101010];
int id[101010],tid=1;
vector<int> cand;

void add(int a,int b,int c) {
	
	int i;
	FOR(i,tid) {
		if(PC[a].count(c)==0 && i&&id[a]==i) uf[i](b,0);
		if(PC[b].count(c)==0 && i&&id[b]==i) uf[i](a,0);
		if(PC[a].count(c)) uf[i](b,PC[a][c]);
		if(PC[b].count(c)) uf[i](a,PC[b][c]);
	}
	
	PC[a][c]=b;
	PC[b][c]=a;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>C>>Q;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>R[i];
		num[U[i]]++;
		num[V[i]]++;
	}
	FOR(i,Q) {
		cin>>T[i]>>X[i]>>Y[i];
		if(T[i]=="+") {
			cin>>Z[i];
			num[X[i]]++;
			num[Y[i]]++;
		}
	}
	
	for(i=1;i<=N;i++) if(num[i]>1000) id[i]=tid++;
	FOR(i,M) add(U[i],V[i],R[i]);
	
	FOR(i,Q) {
		if(T[i]=="?") {
			x=X[i];
			y=Y[i];
			if(uf[0][x]==uf[0][y]) {
				cout<<"Yes"<<endl;
			}
			else if(id[y] && uf[id[y]][x]==uf[id[y]][0]) {
				cout<<"Yes"<<endl;
			}
			else if(id[y]==0) {
				int ok=0;
				FORR(m,PC[y]) if(uf[0][x]==uf[0][m.second]) ok=1;
				if(ok) {
					cout<<"Yes"<<endl;
				}
				else {
					cout<<"No"<<endl;
				}
			}
			else {
				cout<<"No"<<endl;
			}
		}
		else {
			add(X[i],Y[i],Z[i]);;
		}
	}
	
}

まとめ

本番40分以上あったんだしこれは思いついてもよかったのにな。