QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590826#8130. Yet Another Balanced Coloring Problem2020HZ06WA 0ms11912kbC++141.2kb2024-09-26 11:51:112024-09-26 11:51:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 11:51:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11912kb
  • [2024-09-26 11:51:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,leaf[200005],k,ct;
int h[200005];
vector<int>v[200005];
bool vis[400005],ans[100005],b[200005];
struct edge{
	int to,nxt,k;
}e[400005];
void add(int x,int y,int k){
	++ct,e[ct].to=y,e[ct].k=k,e[ct].nxt=h[x],h[x]=ct,vis[ct]=0;
	++ct,e[ct].to=x,e[ct].k=k,e[ct].nxt=h[y],h[y]=ct,vis[ct]=0;
}
int tp;
void dfs(int u){
	if(v[u].size()==0) leaf[u]=1;
	else leaf[u]=0;
	for(int i:v[u]){
		dfs(i),leaf[u]+=leaf[i];
		if(leaf[i]%2==1) add(u,i,tp);
	}
}
void euler(int u){
	b[u]=1;
	for(int i=h[u];i;i=h[u]){
		h[u]=e[i].nxt;
		if(vis[i]) continue;
		if(u<=k){
			if(e[i].k==1) ans[u]=1;
			else ans[u]=0;
		}
		vis[i^1]=1;
		euler(e[i].to);
	}
}
int main(){
	int t,x;
	scanf("%d",&t);
	while(t--){
		ct=1;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n+m;i++) h[i]=b[i]=0,v[i].clear();
		for(int i=1;i<n;i++)
			scanf("%d",&x),v[x].pb(i);
		tp=1,dfs(n);k=leaf[n];
		for(int i=1;i<m;i++)
			scanf("%d",&x),v[x+n-k].pb(i);
		tp=2,dfs(n+m-k);
		euler(n);
		for(int i=1;i<=n+m-k;i++) if(!b[i]) euler(i);
		for(int i=1;i<=k;i++)
			if(ans[i]) printf("R");
			else printf("B");
		printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11912kb

input:

2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4

output:

BRBR
BRB

result:

wrong answer charge of vertex 5 in tree 2 violates range (test case 1)