QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310643#8130. Yet Another Balanced Coloring Problemdo_while_trueWA 17ms16912kbC++142.8kb2024-01-21 16:32:532024-01-21 16:32:53

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-21 16:32:53]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:16912kb
  • [2024-01-21 16:32:53]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int mod=998244353;
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
int qpow(int x,int y){
	int s=1;
	while(y){
		if(y&1)s=1ll*s*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return s;
}
const int N=200010;
int n,m;
int fa[N],siz[N],vis[N],tot,ot[N],ok[N],cur[N];
vi eg[N];
vpii tr[N];
void dfs1(int x){
	if(!eg[x].size()){
		if(x<=n){
			++tot;ot[x]=tot;vis[tot]=0;
			tr[x].pb(x+n,tot);
			tr[x+n].pb(x,tot);
		}
		siz[x]=1;
	}
	for(auto v:eg[x])dfs1(v),siz[x]+=siz[v];
	if(siz[x]&1){
		++tot;vis[tot]=0;
		tr[x].pb(fa[x],tot);
		tr[fa[x]].pb(x,tot);
	}
}
void dfs2(int x){
	ok[x]=1;
	for(int &i=cur[x];i<(int)tr[x].size();i++){
		int v=tr[x][i].fi,id=tr[x][i].se;
		if(!vis[id]){
			vis[id]=x;
			dfs2(v);
		}
	}
}
void solve(){
	read(n,m);
	for(int i=1;i<n;i++)read(fa[i]);
	fa[n]=n+m+1;
	for(int i=n+1;i<n+m;i++)read(fa[i]),fa[i]+=n;
	fa[n+m]=n+m+1;
	for(int i=1;i<=n+m+1;i++)vi().swap(eg[i]),vpii().swap(tr[i]),ot[i]=ok[i]=cur[i]=0;
	for(int i=1;i<=n+m;i++)eg[fa[i]].pb(i);
	tot=0;
	dfs1(n+m+1);
	for(int i=1;i<=n+m+1;i++)
		if(!ok[i])
			dfs2(i);
	for(int i=1;i<=n;i++)if(ot[i])putchar(vis[ot[i]]<=n?'R':'B');
	puts("");
}
signed main(){
	#ifdef do_while_true
//		assert(freopen("data.in","r",stdin));
//		assert(freopen("data.out","w",stdout));
	#endif
	int T;read(T);
	while(T--)solve();
    #ifdef do_while_true
//		cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
	#endif
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16848kb

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:

RBBR
RBR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 17ms
memory: 16912kb

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
RBBRB
RBRBRB
RRR
RBRRB
RRBRR
RRBB
RRBR
RBBRBRR
RBBRBRR
RRR
RBBRBR
RRB
RBRBRBR
RRBBBB
RRRR
RRR
RRRBB
RRB
RRBBR
RRBRR
RBRR
RRRBB
RRR
RBRBR
RRBR
RBRBRR
RRBRBB
RRRR
RRRBBR
RRBRBB
RBRRB
RRBRBB
RBRBRB
RRBBRR
RRR
RRBB
RRR
RRR
RRRBB
RRBB
RBRBRB
RRR
RRRBB
RRR
RBRBRB
RRBRRB
RRR
RBRBRB
RRR
RRB
RBRB
RBRBR
...

result:

wrong answer charge of vertex 5 in tree 1 violates range (test case 4)