QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309507 | #8130. Yet Another Balanced Coloring Problem | ucup-team1631# | Compile Error | / | / | Python3 | 3.7kb | 2024-01-20 17:54:00 | 2024-01-20 17:54:00 |
Judging History
你现在查看的是最新测评结果
- [2024-03-18 02:37:14]
- hack成功,自动添加数据
- (/hack/577)
- [2024-01-20 17:54:00]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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