Codeforces #499 Div1 D. Mars rover

これをすんなり通せたのは良かったね。
http://codeforces.com/contest/1010/problem/D

問題

入力の他AND,OR,XOR,NOTで構成される回路が渡される。
この回路は複数のブール値を入力とし、最終的に単一のブール値を返すようになっている。

複数の入力のそれぞれの値を反転させた場合、出力はどうなるか求めよ。

解法

まず元の入力において各回路の出力を求めよう。
次に、出力から巻き戻す形で「この回路の出力が0/1の場合の最終的な出力」の対を渡していこう。
AND,OR,XORの回路は２つの入力から出力が求めるので、ある入力がどう最終的な出力に影響するかは、その回路自体の出力ともう片方の入力の値から順次巻き戻していくことができる。

int N;
string S[1010101];
int A[1010101],B[1010101];
int in[1010101][2];
int val[1010101];
int ret[1010101];

int dfs(int cur) {
	if(S[cur]=="IN") {
		val[cur]=A[cur];
	}
	else if(S[cur]=="NOT") {
		val[cur]=dfs(A[cur])^1;
	}
	else if(S[cur]=="AND") {
		val[cur]=dfs(A[cur]) & dfs(B[cur]);
	}
	else if(S[cur]=="OR") {
		val[cur]=dfs(A[cur]) | dfs(B[cur]);
	}
	else if(S[cur]=="XOR") {
		val[cur]=dfs(A[cur]) ^ dfs(B[cur]);
	}
	return val[cur];
}

void dfs2(int cur,int v0,int v1) {
	if(S[cur]=="IN") {
		if(A[cur]==0) ret[cur]=v1;
		else ret[cur]=v0;
	}
	else if(S[cur]=="NOT") {
		dfs2(A[cur],v1,v0);
	}
	else if(S[cur]=="AND") {
		dfs2(A[cur],v0,(val[B[cur]]==1)?v1:v0);
		dfs2(B[cur],v0,(val[A[cur]]==1)?v1:v0);
	}
	else if(S[cur]=="OR") {
		dfs2(A[cur],(val[B[cur]]==1)?v1:v0,v1);
		dfs2(B[cur],(val[A[cur]]==1)?v1:v0,v1);
	}
	else if(S[cur]=="XOR") {
		dfs2(A[cur],(val[B[cur]])?v1:v0,(val[B[cur]])?v0:v1);
		dfs2(B[cur],(val[A[cur]])?v1:v0,(val[A[cur]])?v0:v1);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>S[i];
		if(S[i]=="IN" || S[i]=="NOT") {
			cin>>A[i];
		}
		else {
			cin>>A[i]>>B[i];
		}
	}
	
	dfs(1);
	dfs2(1,0,1);
	for(i=1;i<=N;i++) if(S[i]=="IN") cout<<ret[i];
	cout<<endl;
}

まとめ

２回のDFSで1s切ってた。これ5sもいるのかな。