QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590826 | #8130. Yet Another Balanced Coloring Problem | 2020HZ06 | WA | 0ms | 11912kb | C++14 | 1.2kb | 2024-09-26 11:51:11 | 2024-09-26 11:51:11 |
Judging History
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;
}
詳細信息
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)