#C241123C. 旁观者

标签（Label）

网址（Website）

题目详情 - 旁观者 - Super

题解 - 旁观者 - Super

题目（Problem）

题解（Solution）

出题者题解

代码（Code）

15分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int tid,Tt;

vector<int> ft[N];
int n,c[N];

namespace Q{
	void Solve1(){
		int s1=0, s2=0;
		For(i,2,n){
			s1 += c[i]==0;
			s2 += c[i]==1; 
		}printf("%s\n", (s1>s2) ? "yes" : "no");
	}
}

void Solve(){
	For(i,1,n) ft[i].clear();
	
	n=rd();For(x,2,n){
		int y=rd();
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}For(i,1,n) c[i]=rd();
	
	if(in(tid,5,7)) return Q::Solve1();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bystander.in","r",stdin);
	freopen("bystander.out","w",stdout);
	tid=rd();Tt=rd();double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int tid,Tt;

vector<int> ft[N];
int n,c[N],f[N];

void dfs(int x){
	if(ft[x].empty()) return f[x]=c[x]?-1:1, void();
	f[x] = 0;
	for(auto y:ft[x]) dfs(y), f[x] += f[y];
	if(f[x] > 0) f[x]++;
	else if(f[x] < 0) f[x]--;
	else f[x] += n&1?-1:1;
}

void Solve(){
	n=rd();For(i,1,n) ft[i].clear();
	For(x,2,n) ft[rd()].emplace_back(x);
	For(i,1,n) c[i]=rd();
	dfs(1);
	if(f[1]>0) puts("yes");
	else puts("no");
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("bystander.in","r",stdin);
	freopen("bystander.out","w",stdout);
	tid=rd();Tt=rd();double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}