QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364950#8130. Yet Another Balanced Coloring Problemchengning0909TL 2ms10616kbC++171.2kb2024-03-24 17:31:532024-03-24 17:31:53

Judging History

你现在查看的是最新测评结果

  • [2024-03-24 17:31:53]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:10616kb
  • [2024-03-24 17:31:53]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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 ...

output:


result: