记录编号	104641	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[POI 2004]逻辑门	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.186 s
提交时间	2014-06-10 14:20:02	内存使用	0.59 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
//为了方便,我们用-1,0,1代替0,1/2,1
const int SIZEN=10010;
vector<int> out[SIZEN];
int N;
int val[SIZEN]={0};
int insum[SIZEN]={0};
int mn[SIZEN]={0},mx[SIZEN]={0};
queue<int> Q;
bool inq[SIZEN]={0};
void answer(void){
	for(int i=0;i<N;i++){
		if(mn[i]==mx[i]){
			if(mn[i]==-1) printf("0\n");
			else if(mn[i]==0) printf("1/2\n");
			else if(mn[i]==1) printf("1\n");
		}
		else printf("?\n");
	}
}
int sgn(int x){
	if(x>0) return 1;
	if(x<0) return -1;
	return 0;
}
int valid(int x){
	if(x==0) return -1;
	if(x==1) return 1;
	return sgn(insum[x]);
}
void calc_sum(void){//用val计算insum
	memset(insum,0,sizeof(insum));
	for(int i=0;i<N;i++){
		for(int j=0;j<out[i].size();j++) insum[out[i][j]]+=val[i];
	}
}
void balance(void){//此时0和1已经修改恰当,那个刚被修改的在Q中
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		int now=valid(x);
		if(now==val[x]) continue;
		int delta=now-val[x];
		val[x]=now;
		for(int i=0;i<out[x].size();i++){
			int v=out[x][i];
			insum[v]+=delta;
			if(val[v]!=sgn(insum[v])){
				if(!inq[v]){
					inq[v]=true;
					Q.push(v);
				}
			}
		}
	}
}
void work(void){
	for(int i=0;i<N;i++) val[i]=-1;
	calc_sum();
	Q.push(1),inq[1]=true;
	balance();
	memcpy(mn,val,sizeof(val));
	for(int i=0;i<N;i++) val[i]=1;
	calc_sum();
	Q.push(0),inq[0]=true;
	balance();
	memcpy(mx,val,sizeof(mx));
}
void read(void){
	scanf("%d",&N);
	int k,x;
	for(int i=2;i<N;i++){
		scanf("%d",&k);
		for(int j=1;j<=k;j++){
			scanf("%d",&x);
			out[x].push_back(i);
		}
	}
}
int main(){
	freopen("poi2004_bra.in","r",stdin);
	freopen("poi2004_bra.out","w",stdout);
	read();
	work();
	answer();
	return 0;
}