Codeforces #626 Div1 C. Instant Noodles

見かけに対して実装は楽な問題。
https://codeforces.com/contest/1322/problem/C

問題

2N個の頂点からなる左右に分かれた二部グラフが与えられる。
右側の頂点vには値C[v]が設定されている。
左側の頂点から空でない集合Sを選んだ時、N(S)は隣接する右側の頂点の集合とする。
また、f(S)はN(S)に含まれる頂点vにおけるC[v]の総和とする。

Sの取り方全通りにおけるf(S)のGCDを求めよ。

解法

右側の頂点vに対し、隣接する左側の頂点群をTとする。
その時、g(T) += C[v]と同じTに対応する頂点の値の総和を求めよう。
あとはこの値のGCDを取るとよい。

int T,N,M;
ll C[505050];
vector<int> E[505050];
int num[505050];
map<vector<int>,ll> mp;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d\n",&T);
	while(T--) {
		scanf("%d%d\n",&N,&M);
		FOR(i,N) {
			scanf("%lld",&C[i]);
			E[i].clear();
			num[i]=0;
		}
		FOR(i,M) {
			scanf("%d%d\n",&x,&y);
			E[y-1].push_back(x-1);
		}
		mp.clear();
		FOR(i,N) if(E[i].size()) {
			sort(ALL(E[i]));
			mp[E[i]]+=C[i];
		}
		
		ll g=0;
		FORR(m,mp) g=__gcd(g,m.second);
		_P("%lld\n",g);
		
	}
}

まとめ

本番とっさに自信をもって通すの大変そう。