QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309071 | #8130. Yet Another Balanced Coloring Problem | ucup-team1631# | WA | 25ms | 3572kb | C++20 | 3.7kb | 2024-01-20 14:36:24 | 2024-01-20 14:36:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int,int>
#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))
struct ScalarInput {
template<class T>
operator T(){
T ret;
cin >> ret;
return ret;
}
};
struct VectorInput {
size_t n;
VectorInput(size_t n): n(n) {}
template<class T>
operator vector<T>(){
vector<T> ret(n);
for(T &x : ret) cin >> x;
return ret;
}
};
ScalarInput input(){ return ScalarInput(); }
VectorInput input(size_t n){ return VectorInput(n); }
template<typename T>
void print(vector<T> a){
for(int i=0;i<a.size();i++){
cout<<a[i]<<" \n"[i+1==a.size()];
}
}
template<class T>
void print(T x){
cout << x << '\n';
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){
cout << head << ' ';
print(forward<Tail>(tail)...);
}
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>>edge1(n),edge2(m);
rep(i,n-1){
int p;
cin>>p;
p--;
edge1[p].push_back(i);
}
rep(i,m-1){
int p;
cin>>p;
p--;
edge2[p].push_back(i);
}
vector<int>leaf(n,0);
vector<vector<int>>edge3(n);
vector<int>todo;
vector<int>rem(n,-1);
vector<int>par(n,-1);
todo.push_back(n-1);
while(!todo.empty()){
int v=todo.back();
todo.pop_back();
if(v>=0){
for(auto u:edge1[v]){
par[u]=v;
todo.push_back(~u);
todo.push_back(u);
}
}
else{
v=~v;
if((int)edge1[v].size()==0){
rem[v]=v;
leaf[v]=1;
}
if(rem[v]!=-1){
if(rem[par[v]]!=-1){
edge3[rem[v]].push_back(rem[par[v]]);
edge3[rem[par[v]]].push_back(rem[v]);
rem[par[v]]=-1;
}
else{
rem[par[v]]=rem[v];
}
}
}
}
todo.resize(0);
rem.resize(m,-1);
par.resize(m,-1);
todo.push_back(m-1);
while(!todo.empty()){
int v=todo.back();
todo.pop_back();
if(v>=0){
for(auto u:edge2[v]){
par[u]=v;
todo.push_back(~u);
todo.push_back(u);
}
}
else{
v=~v;
if((int)edge2[v].size()==0){
rem[v]=v;
leaf[v]=1;
}
if(rem[v]!=-1){
if(rem[par[v]]!=-1){
edge3[rem[v]].push_back(rem[par[v]]);
edge3[rem[par[v]]].push_back(rem[v]);
rem[par[v]]=-1;
}
else{
rem[par[v]]=rem[v];
}
}
}
}
int k=0;
rep(i,n){
k+=leaf[i];
}
vector<int>seen(k,2);
vector<char>ans(k);
rep(i,k){
if(seen[i]!=2)continue;
seen[i]=0;
vector<int>todo2;
todo2.push_back(i);
while(!todo2.empty()){
int v=todo2.back();
todo2.pop_back();
if(seen[v]==0){
ans[v]='R';
}
else{
ans[v]='B';
}
for(auto u:edge3[v]){
if(seen[u]==2){
seen[u]=seen[v]^1;
todo2.push_back(u);
}
}
}
}
rep(i,k){
cout<<ans[i];
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
rep(T)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
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: 25ms
memory: 3572kb
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 RBRBB RBBRBR RBR RRBRB RRRBB RBBB RBRB RRRBBBB RBRBRBB RBR RBRRBB RBB RBRBRBB RRRBBB RBBB RBR RBBBR RBB RBBRB RBRRB RBRB RBBBR RBB RRBBR RRBB RBBRBB RBBBRR RBRB RBBRRB RBBRRB RRBBB RBRBRB RBBRRB RBRBRB RBB RRBB RBB RBB RRBBB RBBR RBRBRB RBR RBBBR RBR RBRBRB RBRBRB RBR RRBRBB RBR RBR RRBB RBBRB ...
result:
wrong answer charge of vertex 8 in tree 2 violates range (test case 4)