QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310643 | #8130. Yet Another Balanced Coloring Problem | do_while_true | WA | 17ms | 16912kb | C++14 | 2.8kb | 2024-01-21 16:32:53 | 2024-01-21 16:32:53 |
Judging History
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)