QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364955 | #8130. Yet Another Balanced Coloring Problem | chengning0909 | TL | 2ms | 10636kb | C++17 | 1.3kb | 2024-03-24 17:33:24 | 2024-03-24 17:33:24 |
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: 10636kb
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 ...
output:
RBRB RRBBR RBRBR RRB RBRBR RBRBR RRBB RBBB RBRBRB RBBBRBR RBR RBRRB RBB RBBBB RBRBRB RBBB RBB RRBRB RRB RRBRB RBRRB RBBB RBBRB RBR RBBRB RRBB RBRBBR RRBBBB RBRB RRRBBB RBBRBR RBBBB RBRBR RBBRBR RBRBRB RBR RBBR RBR RBR RBBBR RBRB RBRBRB RBR RRBRB RBR RBBBBB RBBRBR RBB RBRBRB RRB RBB RRRB RBRBB RBBR R...