QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#392624 | #8130. Yet Another Balanced Coloring Problem | April_19 | WA | 9ms | 14236kb | C++14 | 2.3kb | 2024-04-17 18:10:29 | 2024-04-17 18:10:29 |
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){
if(p)g[o][p].pb(x);
int siz=(int)e[o][x].size();
for(int y:e[o][x])if(y^fa)dfs1(y,x,siz>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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14236kb
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: 9ms
memory: 14092kb
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:
IMPOSSIBLE BRRBR BRRBRB IMPOSSIBLE BRRRBR IMPOSSIBLE IMPOSSIBLE RBRBBRRB RBRRBBRB BRRBRR BRB RBRBRRBB BRRRBB IMPOSSIBLE RBRBRB RBB BBRBRRRB RBBBR RBBR RBRRBBRR IMPOSSIBLE RB BBRRRBRR IMPOSSIBLE BBRRBR IMPOSSIBLE RRRBBB RBRRB BBRBRR BRRBRB IMPOSSIBLE BRBBRR RRBB RRRBB RRBB BBRBRR RRBB RBRBR IMP...
result:
wrong answer jury has answer, participant doesn't (test case 1)