AtCoder ABC #350 (Promotion of AtCoderJobs) : G - Mediator

これは普通に解けた。
https://atcoder.jp/contests/abc350/tasks/abc350_g

問題

無向グラフを考える。初期状態で辺はない。
以下のクエリに順次答えよ。

• 指定された辺を追加する。なお、辺の追加後もグラフは森であることが保証される。
• 2点U,Vが指定される。UにもVにも辺を持つ点が存在すればそれを答えよ。

解法

平方分割で解く。
もしUかVのいずれかの辺の数がD未満とする。
例えばUの辺の数がD未満の場合、Uに隣接する点を総当たりし、それらがVに隣接するか判定しよう。

それとは別に、「隣接点のうちD本以上の辺を持つ点が2個以上ある」という点を数え上げておく。
そのような点を総当たりし、U,Vを両方含む点がないか判定する。
後者の候補はO(N/D)個程度しかないので、D=√Nとすると全体がO(N√N)程度で済む。

int N,Q;
const ll mo=998244353;

unordered_set<int> E[202020];
int NB[202020];
unordered_set<int> big;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	int ret=0;
	while(Q--) {
		int A,B,C;
		cin>>A>>B>>C;
		A=1+1LL*A*(1+ret)%mo%2;
		B=1+1LL*B*(1+ret)%mo%N;
		C=1+1LL*C*(1+ret)%mo%N;
		
		if(A==1) {
			E[B].insert(C);
			E[C].insert(B);
			if(E[B].size()==1000) {
				FORR(b,E[B]) {
					NB[b]++;
					if(NB[b]==2) big.insert(b);
				}
			}
			if(E[B].size()>1000) {
				NB[C]++;
				if(NB[C]==2) big.insert(C);
			}
			if(E[C].size()==1000) {
				FORR(b,E[C]) {
					NB[b]++;
					if(NB[b]==2) big.insert(b);
				}
			}
			if(E[C].size()>1000) {
				NB[B]++;
				if(NB[B]==2) big.insert(B);
			}
		}
		else {
			if(E[B].size()>=1000&&E[C].size()<1000) swap(B,C);
			ret=0;
			if(E[B].size()<1000) {
				FORR(e,E[B]) if(E[C].count(e)) ret=e;
			}
			else {
				FORR(b,big) if(E[b].count(B)&&E[b].count(C)) ret=b;
			}
			
			
			cout<<ret<<endl;
		}
		
	}
}

まとめ

色々解法ありそうだね。