QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364957 | #8130. Yet Another Balanced Coloring Problem | chengning0909 | WA | 14ms | 11016kb | C++17 | 1.3kb | 2024-03-24 17:33:56 | 2024-03-24 17:33:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, m, c[N];
vector<int> g[2][N], e[N];
int dfs(int id, int u) {
vector<int> p;
for (int v : g[id][u]) {
int k = dfs(id, v);
if (k) p.push_back(k);
}
if (g[id][u].empty()) p.push_back(u);
for (int i = 0; i < p.size(); i += 2) {
e[p[i]].push_back(p[i + 1]);
e[p[i + 1]].push_back(p[i]);
}
return p.size() % 2 ? p[p.size() - 1] : 0;
}
void DFS(int u, int col) {
if (c[u] != -1) return ;
c[u] = col;
for (int v : e[u]) DFS(v, col ^ 1);
}
void Solve() {
cin >> n >> m;
for (int i = 1, fa; i < n; i++) {
cin >> fa, g[0][fa].push_back(i);
}
for (int i = 1, fa; i < m; i++) {
cin >> fa, g[1][fa].push_back(i);
}
dfs(0, n), dfs(1, m);
int cnt = 0;
for (int i = 1; i <= min(n, m) && g[0][i].empty() && g[1][i].empty(); i++, cnt++);
fill(c + 1, c + cnt + 1, -1), DFS(1, 0);
for (int i = 1; i <= cnt; i++) {
cout << (c[i] ? 'B' : 'R'), e[i].clear();
}
cout << '\n';
for (int i = 1; i <= n; i++) g[0][i].clear();
for (int i = 1; i <= m; i++) g[1][i].clear();
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T--) Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10612kb
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 RBB
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 14ms
memory: 11016kb
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 RBBRB RBBBBB RRB RBBBB RRBRB RRBB RBBB RBBRBRR RBBBBBB RBR RBBBBB RBB RBBBBBB RBBBRR RBBB RBB RBRBR RRB RBRBR RBBBR RBBB RBRBB RBR RBBBB RRBB RBBBBB RRBBBB RBBR RBRBRB RBBBBR RBBBB RBRBRB RBBBBB RRBBRB RBR RBBB RBB RBB RBBBB RBBB RBRBRB RRB RBBRB RBB RBBBBB RBBRRB RBB RBRBRB RBB RBB RBRB RBBBB ...
result:
wrong answer charge of vertex 7 in tree 1 violates range (test case 3)