QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#392629#8130. Yet Another Balanced Coloring ProblemApril_19WA 5ms13244kbC++142.4kb2024-04-17 18:17:372024-04-17 18:17:37

Judging History

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

  • [2024-04-17 18:17:37]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:13244kb
  • [2024-04-17 18:17:37]
  • 提交

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)