QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#392629 | #8130. Yet Another Balanced Coloring Problem | April_19 | WA | 5ms | 13244kb | C++14 | 2.4kb | 2024-04-17 18:17:37 | 2024-04-17 18:17:37 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int read(){
int x=0,f=1;char c;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
while(isdigit(c))x=(x<<1)+(x<<3)+(c&15),c=getchar();
return x*f;
}
const int N=1e5+10;
vector<int>e[2][N],g[2][N];
int n,m,leaf,tot,id[N],red[N],blue[N],red_[N],blue_[N];
bool now;
char col[N];
void init(){
for(int i=1;i<=leaf;i++)col[i]=0;
leaf=tot=now=0;
for(int i=1;i<=n;i++){
e[0][i].clear();
g[0][i].clear();
}
for(int i=1;i<=m;i++){
e[1][i].clear();
g[1][i].clear();
}
}
void dfs1(int x,int fa,int p,bool o){
int siz=(int)e[o][x].size();
if(p&&siz!=1){
// cout<<o<<' '<<p<<' '<<x<<endl;
g[o][p].pb(x);
}
for(int y:e[o][x])if(y^fa)dfs1(y,x,(siz+!fa)>1?x:p,o);
}
void dfs2(int x){
bool flag=0;
for(int y:g[0][x]){
if(!(int)g[0][y].size()){
leaf++;
if(!flag)tot+=flag=1;
id[y]=tot;
if(now)blue[tot]++;
else red[tot]++;
now^=1;
}
else dfs2(y);
}
}
//贪心策略:按最小值从小到大排序依次选取。
bool cmp(int x,int y){
int a=min(red[id[x]],blue[id[x]]),b=min(red[id[y]],blue[id[y]]);
if(a!=b)return a<b;
else return id[x]<id[y];// 保证块相同的叶子节点排在一起,避免使用小根堆
}
bool dfs3(int x){
int R=0,B=0;
vector<int>vec;
for(int y:g[1][x]){
if(!(int)g[1][y].size()){
vec.pb(y);
R+=!now,B+=now;
now^=1;
}
else if(!dfs3(y))return 0;
}
sort(vec.begin(),vec.end(),cmp);
for(int y:vec){
int i=id[y];
if(!B){
if(!red[i])return 0;
red[i]--,R--;
col[y]='R';
}
else if(!R){
if(!blue[i])return 0;
blue[i]--,B--;
col[y]='B';
}
else {
if(!red[i]&&!blue[i])return 0;
if(red[i]>blue[i]){
red[i]--,R--;
col[y]='R';
}
else {
blue[i]--,B--;
col[y]='B';
}
}
}
return 1;
}
void solve(){
init();
n=read(),m=read();
for(int i=1;i<n;i++)e[0][read()].pb(i);
for(int i=1;i<m;i++)e[1][read()].pb(i);
dfs1(n,0,0,0);
dfs1(m,0,0,1);
dfs2(n);
for(int i=1;i<=tot;i++)red_[i]=red[i],blue_[i]=blue[i];
now=0;
if(dfs3(m)){
puts(col+1);
return;
}
now=1;
for(int i=1;i<=tot;i++)red[i]=red_[i],blue[i]=blue_[i];
if(dfs3(m)){
puts(col+1);
return;
}
else puts("IMPOSSIBLE");
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("std.out","w",stdout);
int T=read();
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 13244kb
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:
BRRB BRR
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 5ms
memory: 13108kb
input:
10000 6 6 5 5 5 5 6 5 6 6 6 6 9 6 7 9 7 7 6 8 9 9 6 6 6 6 6 9 8 9 9 8 7 7 8 8 9 7 7 8 7 7 7 8 6 10 4 5 5 6 6 4 6 5 7 8 9 8 9 10 6 9 6 6 6 6 6 6 9 7 8 8 9 9 9 8 9 8 6 6 7 6 7 8 7 9 7 6 7 8 9 9 9 8 6 7 7 5 8 8 8 9 7 5 6 5 8 7 8 8 7 6 6 5 5 6 7 8 5 7 6 6 7 7 9 9 8 9 8 8 8 8 9 9 9 9 8 8 9 9 8 9 9 8 8 8 ...
output:
RBRB BRRBR BRRBRB RRB BRRRB IMPOSSIBLE RRBB RBBR BRRRBRB RBBRBRR RBR BRBBRR RRB BRBRRBR RBBBRR BRRB RRB RBRBR RRB BBRRR RRBRB BRBR RRBBR RBR RBRBR BBRR BBRRBR BBRRBR BRBR RBRBRB BBRBRR RBRRB BBRBRR BRRBRB BRBRBR RBR BRRB RRB RRB RRRBB RBBR BRBRBR RRB RBBRR BRR BRBRBR RBBRRB RRB BRBRBR RRB BRR BBRR R...
result:
wrong answer jury has answer, participant doesn't (test case 6)