QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356582 | #8130. Yet Another Balanced Coloring Problem | ucup-team134 | WA | 14ms | 12584kb | C++17 | 4.6kb | 2024-03-18 02:01:41 | 2024-03-18 02:02:51 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}
const int N=2e5+5;
vector<vector<int>> graf(N);
vector<vector<pair<int,int>>> graf2(N);
vector<pair<int,int>> eds;
vector<bool> done(N);
vector<bool> ans(N);
int n,m,k;
void dfs(int tr,int par){
if(tr<k){
eds.pb({tr,par});
return;
}
int cnt=0;
for(auto p:graf[tr]){
cnt++;
dfs(p,tr);
}
if(cnt&1)eds.pb({tr,par});
}
void dfs2(int tr,int par){
if(tr<k){
ans[tr]=par<n;
}
for(auto p:graf2[tr]){
if(done[p.s])continue;
done[p.s]=1;
dfs2(p.f,tr);
}
}
void test(){
scanf("%i %i",&n,&m);
for(int i=0;i<n+m;i++)graf[i].clear(),graf2[i].clear();
eds.clear();
for(int i=0;i<n-1;i++){
int p;
scanf("%i",&p);
p--;
graf[p].pb(i);
}
for(int i=0;i<n;i++){
if(sz(graf[i])!=0||i==n-1){
k=i;
break;
}
}
for(int i=0;i<m-1;i++){
int p;
scanf("%i",&p);
p--;
p+=n;
int ind=i;
if(ind>=k)ind+=n;
graf[p].pb(ind);
}
dfs(n-1,n-1);
dfs(n+m-1,n+m-1);
if(k%2==0){
eds.pb({n-1,n+m-1});
}
//cout << eds << endl;
for(int i=0;i<sz(eds);i++){
done[i]=0;
int a=eds[i].f,b=eds[i].s;
graf2[a].pb({b,i});
graf2[b].pb({a,i});
}
for(int i=k;i<n+m;i++)
dfs2(i,i);
for(int i=0;i<k;i++){
if(ans[i])printf("R");
else printf("B");
}
printf("\n");
}
int main()
{
int t;
scanf("%i",&t);
while(t--)test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 12584kb
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 RBB
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 14ms
memory: 12584kb
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 BBRRR BRRRBB RRB RBRRB BRBRR BBRR RBRB RBBRBRR RBBRBRR RRB RBRBRB RRB RBRBRBR BRRRBB RBRB BRR RRRBB BRR RRRBB BRRBR BRBR RRBBR BRB RBRBR RRBR RBRBRB BRRRBB RBBR RRRBBR RRBRBB RBRRB RRBRBB RBRBRB BRRRBB RBB BRRB BRR RRB RRRBB RBBR BRBRBB RBR RRRBR RRB RBRBRB RRBRRB RBR RBRBRB BBR RRB RBRB RBRBR ...
result:
wrong answer charge of vertex 7 in tree 1 violates range (test case 6)