QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791809 | #8130. Yet Another Balanced Coloring Problem | rizynvu | WA | 9ms | 13908kb | C++14 | 1.2kb | 2024-11-28 21:04:43 | 2024-11-28 21:04:44 |
Judging History
answer
#include<bits/stdc++.h>
constexpr int maxn = 2e5 + 10;
std::vector<int> son[maxn], to[maxn];
int k, pr[maxn];
void dfs(int u) {
if (son[u].empty()) {
pr[u] = u, k++;
} else {
for (int v : son[u]) {
dfs(v);
if (pr[u] && pr[v]) {
to[pr[u]].push_back(pr[v]);
to[pr[v]].push_back(pr[u]);
pr[u] = 0;
} else {
pr[u] |= pr[v];
}
}
}
}
inline void solve(int n) {
for (int i = 1; i <= n; i++) son[i].clear();
for (int i = 1, f; i < n; i++) {
scanf("%d", &f), son[f].push_back(i);
}
dfs(n);
}
int col[maxn];
void dfsc(int u, int c) {
if (col[u]) return ;
col[u] = c;
for (int v : to[u]) {
dfsc(v, 3 - c);
}
}
inline void solve() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) to[i].clear();
k = 0;
solve(n), solve(m);
k >>= 1;
memset(col + 1, 0, sizeof(int) * k);
for (int i = 1; i <= k; i++) {
dfsc(i, 1);
putchar(" RB"[col[i]]);
}
puts("");
}
int main() {
for (int T, _ = scanf("%d", &T); T--; ) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13484kb
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: 9ms
memory: 13908kb
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 RRRBBR RRB RBRRB RBRRB RRBB RBBR RBBRBRB RBRBRBR RRR RRBBBR RRB RBRBRBR RRBBRB RRRB RRB RBBRR RRB RBBRB RBBRR RBRB RRBRB RRB RRBBR RRBB RBRBRB RBRRBB RBRR RBRBRB RBBRBR RRBBR RBRBRB RBRBRB RRRRBB RRB RRBB RBR RRB RBRBB RBRB RBRBRB RRB RBBRR RRB RBRRBB RBRBBR RRR RRBRBR RRB RRB RBRB RBRBR ...
result:
wrong answer charge of vertex 7 in tree 1 violates range (test case 3)