QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#322439 | #8130. Yet Another Balanced Coloring Problem | bachbeo2007 | WA | 4ms | 3712kb | C++23 | 2.9kb | 2024-02-07 00:41:40 | 2024-02-07 00:41:41 |
Judging History
answer
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=500005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
const int iroot=power(3,mod-2);
const int base=101;
/*
2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4
*/
bool check[maxn];
vector<pii> edge[maxn];
char col[maxn];
int n,m,k;
void dfs(int u){
while(!edge[u].empty()){
if(check[edge[u].back().se]) edge[u].pop_back();
else{
auto [v,id]=edge[u].back();
edge[u].pop_back();check[id]=true;
if(v<=k) col[v]=(u<=n?'R':'B');
dfs(v);
}
}
}
void solve(){
cin >> n >> m;k=n;
for(int i=0;i<=n+m;i++) edge[i].clear();
int pos=0;
for(int i=1;i<n;i++){
int p;cin >> p;
k=min(k,p-1);
edge[i].push_back({p,pos});
edge[p].push_back({i,pos++});
}
for(int i=1;i<m;i++){
int p;cin >> p;p+=n-k;
int v=i+(i>k)*(n-k);
edge[v].push_back({p,pos});
edge[p].push_back({v,pos++});
}
int N=n+m-k;
for(int i=1;i<=N;i++){
if((int)edge[i].size()&1){
edge[0].push_back({i,pos});
edge[i].push_back({0,pos++});
}
}
dfs(1);
for(int i=1;i<=k;i++) cout << col[i];
cout << '\n';
for(int i=0;i<pos;i++) check[i]=false;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;cin >> test;
while(test--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
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: 4ms
memory: 3712kb
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 RRBBR RBBRBR RBR RBRBR RRBBR RRBB RBBR RRBRBRB RBRBRBR RBR RBRBRB RBR RBBRBRR RBRBBR RBRB RRB RBBBR RBR RBBRR RRBBR RBRB RBBRR RBR RBRBR RRBB RBBRBR RBBBRR RBBR RBBBRR RBBBRR RBBRR RBRBRB RBBRBR RBBBRR RBR RBBR RRB RBR RBBRB RBBR RBRBRB RRB RBBRB RBR RBRBRB RBRBRB RBR RBRBRB RBR RBR RRBB RBBRR ...
result:
wrong answer charge of vertex 8 in tree 2 violates range (test case 4)