QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364957#8130. Yet Another Balanced Coloring Problemchengning0909WA 14ms11016kbC++171.3kb2024-03-24 17:33:562024-03-24 17:33:56

Judging History

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

  • [2024-03-24 17:33:56]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:11016kb
  • [2024-03-24 17:33:56]
  • 提交

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: 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)