QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#322436#8130. Yet Another Balanced Coloring Problembachbeo2007WA 10ms3684kbC++232.9kb2024-02-07 00:31:302024-02-07 00:31:30

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-02-07 00:31:30]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3684kb
  • [2024-02-07 00:31:30]
  • 提交

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[i].push_back({p,pos});
        edge[p].push_back({i,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: 3684kb

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: 10ms
memory: 3644kb

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
RBBBR
RBBBR
RRBB
RBBR
RRBRBBB
RBRBRBR
RBB
RBRBBB
RBR
RBBRBRR
RRRBBB
RBBB
RBB
RBBRB
RBB
RBBBB
RBBBB
RBRB
RBBBR
RBB
RBRBB
RBBB
RBBRBB
RBBBRR
RBBB
RBBBRB
RBBBRR
RBBRR
RBRBRB
RBBRBR
RBBBRR
RBB
RBBR
RRB
RBB
RBBRB
RBBB
RBRBRB
RRB
RBBRB
RBB
RBRBRB
RBBRRB
RBB
RBRBRB
RBB
RBB
RRBB
RBBRB
...

result:

wrong answer charge of vertex 8 in tree 2 violates range (test case 4)