QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#350906 | #8130. Yet Another Balanced Coloring Problem | Charizard2021 | WA | 28ms | 3592kb | C++17 | 2.3kb | 2024-03-11 09:42:00 | 2024-03-11 09:42:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
// get representive component (uses path compression)
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
};
int main(){
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<int> p(n - 1);
int k = n;
for(int i = 0; i < n - 1; i++){
cin >> p[i];
p[i]--;
k = min(k, p[i]);
}
vector<int> q(m - 1);
for(int i = 0; i < m - 1; i++){
cin >> q[i];
q[i]--;
}
DSU dsu(k * 2);
vector<int> thing(n, -1);
for(int i = 0; i < k; i++){
thing[i] = i;
}
for(int i = 0; i < n - 1; i++){
if(thing[i] != -1){
if(thing[p[i]] == -1){
thing[p[i]] = thing[i];
}
else{
int u = thing[i];
int v = thing[p[i]];
thing[v] = -1;
dsu.unite(2 * u, 2 * v + 1);
dsu.unite(2 * u + 1, 2 * v);
}
}
}
vector<int> thing2(m, -1);
for(int i = 0; i < k; i++){
thing2[i] = i;
}
for(int i = 0; i < m - 1; i++){
if(thing2[i] != -1){
if(thing2[q[i]] == -1){
thing2[q[i]] = thing2[i];
}
else{
int u = thing2[i];
int v = thing2[q[i]];
thing2[v] = -1;
dsu.unite(2 * u, 2 * v + 1);
dsu.unite(2 * u + 1, 2 * v);
}
}
}
for(int i = 0; i < k; i++){
if(dsu.get(2 * i) % 2 == 1){
cout << "R";
}
else{
cout << "B";
}
}
cout << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3484kb
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 RBB
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 3592kb
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:
BBBB RRRRR RRRRRR BBB BBBBB RRRRR RRRR RRRR BBBBBBB BBBBBBB BBB BBBBBB BRB BBBBBBB RRRRRR BBBB RBB BBBBB BBB RBBBB RRRRR RRRR BBBBB BBB RBBBB BBBB BBBBBB BBBBBB RRRR BBBBBB BBBBBB BBBBB BBBBBB RBBBBB BBBBBB BBB RRRR BBB BRB BBBBB RBBR BBBBBB BBB RRRRR RBB RBBBBB BBBBBB BBB BBBBBB BBB RBB BBBB BBBBB ...
result:
wrong answer charge of vertex 5 in tree 1 violates range (test case 1)