AtCoder ARC #144 : E - GCD of Path Weights

これあんまり記憶にないな。
https://atcoder.jp/contests/arc144/tasks/arc144_e

問題

N点M辺の有向グラフを考える。
このグラフは、頂点番号の小さい方から大きい方に辺が向いており、かつ1番の頂点から各辺にパスが存在する。

一部の点は重さが定められており、残りは不定とする。
不定の点の重さを任意の正整数とできるとき、1番の頂点からN番の点に至るパスの点の重みの操作のGCDの最大値を求めよ。

解法

点を2つに分解して、点の重さをその2点間の辺の重みとして表現しよう。
以後、点ではなく辺の重みを考える。
また、1番からN番のパス上に通りえない頂点は無視する。

各点のポテンシャルを、定めることを考える。
不定でない重さの辺を無向辺とみなし、union-findの要領で点を連結していく。
その際、連結成分内で基準となる点とのポテンシャルの差分を、マージテクの要領で管理していき、閉路ができた場合はそれらのGCDを取れば解となる。

int N,M;
vector<int> E[404040][2];
int vis[404040][2];
ll A[303030];

int id[603030];
set<int> C[603030];
ll D[603030];
ll G;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1][0].push_back(y-1);
		E[y-1][1].push_back(x-1);
	}
	FOR(i,N) cin>>A[i];
	
	vis[0][0]=1;
	FOR(i,N) FORR(e,E[i][0]) vis[e][0]|=vis[i][0];
	vis[N-1][1]=1;
	for(i=N-1;i>=0;i--) FORR(e,E[i][1]) vis[e][1]|=vis[i][1];
	
	FOR(i,N) {
		
		if(A[i]==-1) {
			id[i*2]=i*2;
			id[i*2+1]=i*2+1;
			C[i*2]={i*2};
			C[i*2+1]={i*2+1};
		}
		else {
			id[i*2]=id[i*2+1]=i*2;
			C[i*2]={i*2,i*2+1};
			D[i*2+1]=A[i];
		}
	}
	FOR(i,N) if(vis[i][0]&&vis[i][1]) {
		FORR(e,E[i][0]) if(vis[e][0]&&vis[e][1]) {
			if(id[i*2+1]!=id[2*e]) {
				x=id[i*2+1];
				y=id[2*e];
				ll dif=D[i*2+1]-D[2*e];
				if(C[x].size()<C[y].size()) swap(x,y), dif=-dif;
				FORR(v,C[y]) {
					C[x].insert(v);
					id[v]=x;
					D[v]+=dif;
				}
				
			}
			else {
				G=__gcd(G,abs(D[2*e]-D[i*2+1]));
			}
			
		}
	}
	
	if(id[0]==id[2*N-1]) {
		G=__gcd(G,abs(D[0]-D[2*N-1]));
	}
	
	if(G==0) G=-1;
	cout<<G<<endl;
}

まとめ

これは今思えばそこまで難しくはないのかも。