QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
详细
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)