QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429327#8130. Yet Another Balanced Coloring Problemlmeowdn#WA 5ms17604kbC++142.1kb2024-06-02 11:50:382024-06-02 11:50:38

Judging History

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

  • [2024-06-02 11:50:38]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:17604kb
  • [2024-06-02 11:50:38]
  • 提交

answer

//Shirasu Azusa 2024.6
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=3e5+5;
int n,m,k,p[N],q[N],f[N],deg[N],g[N],tot,vst[N],r[N];
vp e[N];

void dfs(int u) {
  while(e[u].size()) {
    auto [v,d]=e[u][e[u].size()-1]; e[u].pop_back();
    if(vst[d]) continue;
    vst[d]=v+N; dfs(v);
  }
}

void work() {
  n=read(), m=read();
  rep(i,1,n) p[i]=f[i]=0;
  rep(i,1,m) q[i]=g[i]=0;
  rep(i,1,n) deg[i]=0;
  rep(i,1,n-1) p[i]=read(), deg[p[i]]++;
  int k=1; while(k<=n&&deg[k]==0) k++; k--;
  rep(i,1,m-1) q[i]=read();
  rep(i,1,k) f[i]=g[i]=1;
  rep(i,1,n) f[p[i]]+=f[i];
  rep(i,1,m) g[q[i]]+=g[i];
  tot=1;
  rep(i,1,n) if(f[i]&1) {
    ++tot; if(i<=k) r[i]=tot;
    e[p[i]].eb(i,tot), e[i].eb(p[i],tot);
  }
  rep(i,1,m) if(g[i]&1) {
    ++tot; int x=(i<=k?i:i+m);
    e[q[i]+m].eb(x,tot), e[x].eb(q[i]+m,tot);
  }
  rep(i,1,tot) vst[i]=0;
  rep(i,0,n+m) dfs(i);
  rep(i,1,k) {
    if(vst[r[i]]-N==i) putchar('R');
    else putchar('B');
  } puts("");
}


signed main() {
  int T=read(); while(T--) work();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
BRR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 16828kb

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
RRBBB
RBBRBR
RRB
BRRBR
RRBBR
RRBB
RBRB
RBBRBRB
BRRBRBB
RBR
RBRBRB
BBR
RBBRBRR
RBRBBR
RBRB
RRB
BBRRR
BBR
BBRRR
RRBBR
RBRB
BBRRR
BRB
BRBRR
RRBB
RBBRBR
RBBBRR
RBRB
RBBBRR
RBBBRR
RBBRR
RBRBRB
RBBRBR
RBBBRR
BRR
RBBR
BBB
RBR
BRBRR
RRBB
RRBRBB
BBB
RRBRB
RBB
RBRBRB
RBRBRB
RRB
RBRBRB
RBR
BRR
RRBB
BRRBR
...

result:

wrong answer charge of vertex 10 in tree 1 violates range (test case 38)