QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#322439#8130. Yet Another Balanced Coloring Problembachbeo2007WA 4ms3712kbC++232.9kb2024-02-07 00:41:402024-02-07 00:41:41

Judging History

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

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

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();
}

詳細信息

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)