QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#392624#8130. Yet Another Balanced Coloring ProblemApril_19WA 9ms14236kbC++142.3kb2024-04-17 18:10:292024-04-17 18:10:29

Judging History

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

  • [2024-04-17 18:10:29]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:14236kb
  • [2024-04-17 18:10:29]
  • 提交

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;
}

詳細信息

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)