Codeforces Global Round 17 : F. Mashtali: a Space Oddysey

本番苦戦してはいるもののどうにか解き切ってる。
https://codeforces.com/contest/1610/problem/F

問題

無向グラフが与えられる。
各辺の重みは1か2である。
この辺に、向きをつけることを考える。
頂点vが美しいとは、入る辺の重みの総和と、出る辺の重みの総和の差の絶対値が1であることを意味する。

美しい頂点数を最大化する辺の向きの付け方を求めよ。

解法

各点に接続する辺の重さの和が奇数なら、その頂点はどうにか上記絶対値を1にすることを考える。
これが達成できれば明らかに最大化できる。

まず同じ重さの辺からなるパスに分解しよう。
パス内の各辺は同じ向きにすると考えると、パスを構成する各辺の向きを決めることは、結局パスの始点と終点の間に張った辺の向きを決めることに等しい。
よって、元のパスを、この新たな辺に置き換えよう。
また、この時各点に同じ重さの辺が2個付くことはない。

あとはこの置き換えた辺からなるグラフをDFSし、入る辺の重みと出る辺の重みの差が+1/-1どちらになるか割り当てていこう。

int N,M;
set<pair<int,int>> E[202020][2];
set<pair<int,int>> E2[202020];
int sum[202020];
int U[202020],V[202020],W[202020],ret[202020];
int num[202020];
int C[202020];

map<pair<int,int>,vector<pair<int,int>>> memo[2];

void dfs(int cur,int id,vector<pair<int,int>>& R) {
	if(E[cur][id].empty()) {
		return;
	}
	auto e=*E[cur][id].begin();
	E[cur][id].erase(E[cur][id].begin());
	E[e.first][id].erase({cur,e.second});
	R.push_back({e.first,e.second});
	dfs(e.first,id,R);
}

void dfs2(int cur) {
	if(E2[cur].empty()) {
		return;
	}
	auto e=*E2[cur].begin();
	E2[cur].erase(E2[cur].begin());
	int nex=e.first;
	int id=e.second;
	E2[nex].erase({cur,id});
	
	int x,y;
	if(memo[id].count({cur,nex})) {
		vector<pair<int,int>> R=memo[id][{cur,nex}];
		for(x=1;x<R.size();x++) {
			y=R[x].second;
			ret[y]=1+(V[y]==R[x].first);
		}
	}
	else {
		assert(memo[id].count({nex,cur}));
		vector<pair<int,int>> R=memo[id][{nex,cur}];
		for(x=R.size()-1;x>=1;x--) {
			y=R[x].second;
			ret[y]=1+(V[y]!=R[x].first);
		}
	}
	
	dfs2(nex);
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--,V[i]--,W[i]--;
		E[U[i]][W[i]].insert({V[i],i});
		E[V[i]][W[i]].insert({U[i],i});
		if(W[i]==0) sum[U[i]]^=1,sum[V[i]]^=1;
	}
	
	FOR(i,2) {
		FOR(j,N) if(E[j][i].size()%2==1) {
			vector<pair<int,int>> R;
			R.push_back({j,-1});
			dfs(j,i,R);
			x=R.back().first;
			memo[i][{j,x}]=R;
			/*
			cout<<i<<" "<<j<<" "<<x<<" ";
			FORR(r,R) cout<<r.first<<":"<<r.second<<" ";
			cout<<endl;
			*/
			E2[j].insert({x,i});
			E2[x].insert({j,i});
		}
	}
	FOR(i,2) {
		FOR(j,N) while(E[j][i].size()) {
			vector<pair<int,int>> R;
			R.push_back({j,-1});
			dfs(j,i,R);
			for(x=1;x<R.size();x++) {
				y=R[x].second;
				ret[y]=1+(V[y]==R[x].first);
			}
		}
	}
	FOR(i,N) if(E2[i].size()%2==1) dfs2(i);
	FOR(i,N) dfs2(i);
	
	int num=0;
	FOR(i,N) num+=sum[i];
	FOR(i,M) {
		assert(ret[i]>=1);
		if(ret[i]==1) {
			C[U[i]]-=W[i]+1;
			C[V[i]]+=W[i]+1;
		}
		else {
			C[V[i]]-=W[i]+1;
			C[U[i]]+=W[i]+1;
		}
	}
	FOR(i,N) {
		if(C[i]%2) assert(abs(C[i])==1);
	}
	
	
	cout<<num<<endl;
	FOR(i,M) cout<<ret[i];
	cout<<endl;
	
}

まとめ

手間取ったけど時間内に解き切れてよかった。