Codeforces Round #499 (Div. 2): F. Mars rover（DFS）

 

题意：给你一个门电路（包含XOR、OR、AND、NOT、IN五种），这个门电路构成了一棵树，其中1号是输出端（根），所有的叶子都是输入端，给出每个节点（门）的功能以及输入端的输入（是0还是1），求出在只改变任何一个输入端的情况下，输出端分别输出1还是0

 

只关心AND门和OR门，对于AND门，如果左儿子值为0，那么右子树所有叶子值的改变都不会影响输出，如果右儿子值为0，那么左子树所有叶子值的改变都不会影响输出，对于OR门同理

所以只要1~2遍DFS就可以求出每一个叶子的改变是否对答案产生影响

 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct
{
	int x, y, id;
	char str[15];
}Point;
Point s[1000005];
int ans[1000005], flag[1000005];
int Sech(int u)
{
	int i, p1, p2;
	if(s[u].str[1]=='I')
		return s[u].x;
	if(s[u].str[1]=='N')
		return Sech(s[u].x)^1;
	if(s[u].str[1]=='X')
		return Sech(s[u].x)^Sech(s[u].y);
	if(s[u].str[1]=='A')
	{
		p1 = Sech(s[u].x), p2 = Sech(s[u].y);
		if(p1==0)
			flag[s[u].y] = 1;
		if(p2==0)
			flag[s[u].x] = 1;
		return p1&p2;
	}
	if(s[u].str[1]=='O')
	{
		p1 = Sech(s[u].x), p2 = Sech(s[u].y);
		if(p1==1)
			flag[s[u].y] = 1;
		if(p2==1)
			flag[s[u].x] = 1;
		return p1|p2;
	}
	printf("WA\n");
	return -1;
}
void Sech2(int u)
{
	int i, p1, p2;
	if(flag[u])
		return;
	if(s[u].str[1]=='I')
		ans[s[u].id] = 1;
	if(s[u].str[1]=='N')
		Sech2(s[u].x);
	if(s[u].str[1]=='X' || s[u].str[1]=='A' || s[u].str[1]=='O')
	{
		Sech2(s[u].x);
		Sech2(s[u].y);
	}
}
int main(void)
{
	int n, i, now;
	scanf("%d", &n);
	memset(ans, -1, sizeof(ans));
	for(i=1;i<=n;i++)
	{
		scanf("%s", s[i].str+1);
		if(s[i].str[1]=='I' || s[i].str[1]=='N')
			scanf("%d", &s[i].x);
		else
			scanf("%d%d", &s[i].x, &s[i].y);
		s[i].id = i;
		if(s[i].str[1]=='I')
			ans[i] = 0;
	}
	now = Sech(1);
	Sech2(1);
	for(i=1;i<=n;i++)
	{
		if(ans[i]==-1)
			continue;
		printf("%d", now^ans[i]);
	}
	puts("");
	return 0;
}