QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309507#8130. Yet Another Balanced Coloring Problemucup-team1631#Compile Error//Python33.7kb2024-01-20 17:54:002024-01-20 17:54:00

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-20 17:54:00]
  • 评测
  • [2024-01-20 17:54:00]
  • 提交

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.assign(0,0);
  rem.assign(m,-1);
  par.assign(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

  File "answer.code", line 2
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax