QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364950 | #8130. Yet Another Balanced Coloring Problem | chengning0909 | TL | 2ms | 10616kb | C++17 | 1.2kb | 2024-03-24 17:31:53 | 2024-03-24 17:31:53 |
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');
}
cout << '\n';
}
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: 10616kb
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
Time Limit Exceeded
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 ...