QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323892#8130. Yet Another Balanced Coloring Problemucup-team055#WA 17ms3616kbC++171.4kb2024-02-10 14:02:242024-02-10 14:02:25

Judging History

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

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

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define all(p) p.begin(),p.end()
using ll =long long;

struct uf{
    int n;
    vector<int> par;
    uf(int n_):n(n_){
        par.resize(n);
        rep(i,0,n) par[i]=i;
    }
    int root(int a){
        if(a==par[a]) return a;
        par[a]=root(par[a]);
        return par[a];
    }
    int unite(int a,int b){
        a=root(a),b=root(b);
        if(a==b) return 0;
        if(a>b) swap(a,b);
        par[b]=a;
        return 1;
    }
};

void solve(){
    int N,M;
    cin>>N>>M;
    vector<int> p(N-1),q(M-1);
    int K=N;
    rep(i,0,N-1) cin>>p[i],p[i]--,K=min(p[i],K);
    rep(i,0,M-1) cin>>q[i],q[i]--,K=min(q[i],K);
    uf T(K*2);
    auto f=[&](ll n,vector<int> v) -> void {
        vector<int> tmp(n,-1);
        rep(i,0,K){
            tmp[i]=i;
        }
        rep(i,0,n-1){
            if(tmp[i]==-1) continue;
            if(tmp[v[i]]==-1) tmp[v[i]]=tmp[i];
            else{
                int a=tmp[i],b=tmp[v[i]];
                tmp[v[i]]=-1;
                T.unite(2*a,2*b+1);
                T.unite(2*a+1,2*b);
            }
        }
    };
    f(N,p),f(M,q);
    rep(i,0,K) cout<<(T.root(i)&1?'R':'B');
    cout<<"\n";
}

int main(){
    int T;
    cin>>T;
    while(T--) solve();
}

/*
2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4
 */

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

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:

BRRB
BRR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 17ms
memory: 3552kb

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:

BRRB
BRRBR
BRRBBR
BRB
BRRBB
BRBRR
BRBR
BRRB
BRRBRBB
BRRBBRR
BRR
BRRBBR
BRB
BRRBBRR
BRRBRB
BRRB
BRB
BRRBB
BRB
BRRBB
BRBRR
BRRB
BRRBB
BRR
BRRBB
BRBR
BRRBBR
BRBRRB
BRRB
BRRBBR
BRRBRB
BRRBB
BRRBBR
BRRBBR
BRBRRB
BRR
BRBR
BRB
BRB
BRRBB
BRBR
BRRBBR
BRB
BRBRR
BRR
BRRBBR
BRRBRB
BRB
BRRBBR
BRB
BRR
BRRB
BRRBB
...

result:

wrong answer charge of vertex 7 in tree 1 violates range (test case 3)