Google Code Jam 2019 Round 2 : D. Contransmutation

本番適当にやったらSmallすら通らなかったが、真面目にやったら自力で通せた。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/0000000000146185

問題

N種類の金属がある。
あるi番の金属1グラムを分解すると、X[i]番とY[i]番の金属が1グラムずつできる（質量保存則は無視する)。
X[i]!=Y[i]だが、X[i]やY[i]がiに一致することもある。

初期状態で各金属の重さが与えられる。
最適な順で最適な量金属を分解した場合、1番の金属をどれだけ生成できるか。

解法

分解の関係を有向辺で表すと閉路ができる可能性がある。
そこでまず強連結成分分解しよう。
各成分につき、以下の特徴が現れる。

• n頂点の連結成分にn辺がある場合、いったんこの連結成分内の金属が1グラムでもできると、閉路内をぐるぐる分解することで、閉路内の総質量は変化しないが閉路の外側に対しては無限量の金属を生成できる。
• n頂点の連結成分に(n+1)辺以上がある場合、いったんこの連結成分内の金属が1グラムでもできると、閉路内でぐるぐる分解することで閉路内含め無限の金属を生成できる。

あとはトポロジカルソート順に、1番の金属を含まない連結成分については順次分解していけばよい。
その際、各連結成分は無限量の金属の生成が可能かもフラグを持っておこう。

途中加算の過程で重さが(10^9+7)グラムになることがあるので、modの処理の過程で誤って0グラムとみなさないようにしておこう。

public:
	static const int MV = 105000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

int M,N;
ll R[2][101010];
ll G[101010],G2[101010],hasinf[101010];
ll mo=1000000007;
SCC scc;
int GRm[101010];
vector<int> E[101010];
int in[101010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>M;
	scc.init(M);
	FOR(i,M) {
		cin>>R[0][i]>>R[1][i];
		R[0][i]--;
		R[1][i]--;
		scc.add_edge(i,R[0][i]);
		scc.add_edge(i,R[1][i]);
		E[i].clear();
	}
	FOR(i,M) cin>>G[i];
	
	scc.scc();
	ZERO(GRm);
	ZERO(G2);
	ZERO(hasinf);
	ZERO(in);
	N=scc.SC.size();
	FOR(i,M) {
		if(scc.GR[i]==scc.GR[R[0][i]] && scc.GR[i]==scc.GR[R[1][i]]) GRm[scc.GR[i]]|=2;
		if(scc.GR[i]==scc.GR[R[0][i]] || scc.GR[i]==scc.GR[R[1][i]]) GRm[scc.GR[i]]|=1;
		if(scc.GR[i]!=scc.GR[R[0][i]]) E[scc.GR[i]].push_back(scc.GR[R[0][i]]), in[scc.GR[R[0][i]]]++;
		if(scc.GR[i]!=scc.GR[R[1][i]]) E[scc.GR[i]].push_back(scc.GR[R[1][i]]), in[scc.GR[R[1][i]]]++;
		G2[scc.GR[i]]+=G[i];
	}
	
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		
		if(G2[x] && (GRm[x]&2)) hasinf[x]=1;
		if(G2[x]) {
			G2[x]%=mo;
			if(G2[x]==0) G2[x]=mo;
		}
		if(scc.GR[0]==x) break;
		if(G2[x]!=0 && (GRm[x]&1)) hasinf[x]=1;
		
		
		FORR(e,E[x]) {
			hasinf[e]|=hasinf[x];
			G2[e]+=G2[x];
			if(--in[e]==0) Q.push(e);
		}
	}
	
	
	if(hasinf[scc.GR[0]]) {
		_P("Case #%d: UNBOUNDED\n",_loop);
	}
	else {
		_P("Case #%d: %lld\n",_loop,G2[scc.GR[0]]%mo);
	}
}

まとめ

Cよりこっちやっておけばよかった。