QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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...