QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309071#8130. Yet Another Balanced Coloring Problemucup-team1631#WA 25ms3572kbC++203.7kb2024-01-20 14:36:242024-01-20 14:36:25

Judging History

This is the latest submission verdict.

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-20 14:36:25]
  • Judged
  • Verdict: WA
  • Time: 25ms
  • Memory: 3572kb
  • [2024-01-20 14:36:24]
  • Submitted

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)