Codeforces ECR #106 : G. Graph Coloring

変な出力形式の問題。
https://codeforces.com/contest/1499/problem/G

問題

二部グラフが与えられる。
また、クエリで辺がさらに追加される。

各状態について、以下を答えよ。

• 各辺を赤青で塗り分ける。その際、各頂点のコストはその頂点を端点とする辺のうち、赤辺と青辺の数の差とする。
• コストの総和の最小値を達成する塗り分け方のハッシュ値を答えよ。なお、この問題はインラインであり、何度かハッシュ値を再現する塗り分け方を実際に答えてもらう。

解法

二部グラフ中にサイクルができたら、そのサイクルの辺を赤青交互に塗り分けたとすると、そのサイクルによるコストは0となり、以後そのサイクルは無視できる。
また、パスが1個あると、同様に辺を赤青交互に塗り分ければ、両端でコストが1かかるだけとなる。

そこで、グラフをパスの集合として管理しよう。
問題点として、クエリで辺を追加することで、既存の2パスをつなぎ連結することになるが、場合によっては赤青交互にならないようなつながり方をする可能性がある。
その場合、マージテクの要領で元々短い方のパスを赤青反転してつじつまを合わせよう。

int A,B,M,Q;
deque<int> D[404040];
int U[404040],V[404040];
pair<int,int> E[404040]; //末尾と辺index
int col[404040];
ll p2[404040];
const ll mo=998244353;

ll ret=0;

void add(int i,int x,int y) {
	y+=200000;
	U[i]=x;
	V[i]=y;
	int k,r;
	if(E[x].first==y) {
		//connect
		k=E[x].second;
		col[i]=col[D[k][0]]^1;
		if(col[i]==1) ret+=p2[i];
		E[x]=E[y]={0,0};
	}
	else if(E[x].first&&E[y].first) {
		int ox=E[x].first;
		int oy=E[y].first;
		k=E[x].second;
		r=E[y].second;
		
		if(D[k].size()<=D[r].size()) {
			swap(k,r);
			swap(x,y);
			swap(ox,oy);
		}
		
		if(U[r]!=y) reverse(ALL(D[r]));
		
		if(U[k]==x) {
			int cur=col[D[k][0]];
			D[k].push_front(i);
			cur^=1;
			col[i]=cur;
			if(col[i]) ret+=p2[i];
			
			FORR(v,D[r]) {
				if(col[v]) ret-=p2[v];
				cur^=1;
				col[v]=cur;
				if(col[v]) ret+=p2[v];
				D[k].push_front(v);
			}
			U[k]=oy;
		}
		else {
			int cur=col[D[k].back()];
			D[k].push_back(i);
			cur^=1;
			col[i]=cur;
			if(col[i]) ret+=p2[i];
			
			FORR(v,D[r]) {
				if(col[v]) ret-=p2[v];
				cur^=1;
				col[v]=cur;
				if(col[v]) ret+=p2[v];
				D[k].push_back(v);
			}
			V[k]=oy;
		}
		E[x]=E[y]={0,0};
		E[ox]={oy,k};
		E[oy]={ox,k};
		D[r].clear();
		
	}
	else if(E[x].first||E[y].first) {
		if(E[y].first) swap(x,y);
		int o=E[x].first;
		k=E[x].second;
		if(U[k]==x) {
			r=D[k][0];
			col[i]=col[r]^1;
			if(col[i]) ret+=p2[i];
			D[k].push_front(i);
			U[k]=y;
		}
		else {
			r=D[k].back();
			col[i]=col[r]^1;
			if(col[i]) ret+=p2[i];
			D[k].push_back(i);
			V[k]=y;
		}
		E[o]={y,k};
		E[x]={0,0};
		E[y]={o,k};
	}
	else {
		D[i].push_back(i);
		E[x]={y,i};
		E[y]={x,i};
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,401010) {
		p2[i+1]=p2[i]*2%mo;
	}
	
	cin>>A>>B>>M;
	for(i=1;i<=M;i++) {
		cin>>x>>y;
		add(i,x,y);
	}
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			M++;
			add(M,x,y);
			ret=(ret%mo+mo)%mo;
			cout<<ret<<endl;
		}
		else {
			int c=0;
			for(i=1;i<=M;i++) c+=col[i];
			cout<<c;
			for(i=1;i<=M;i++) if(col[i]) cout<<" "<<i;
			cout<<endl;
		}
	}
	
	
}

まとめ

考え方は難しくないけど、地味に実装が面倒くさい。