QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622778#8130. Yet Another Balanced Coloring Problemucup-team1766RE 1ms3812kbC++202.3kb2024-10-09 05:29:262024-10-09 05:29:27

Judging History

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

  • [2024-10-09 05:29:27]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3812kb
  • [2024-10-09 05:29:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int build_graph(int n, int k, bool is_one, vector<vector<int>> &tree, vector<set<int>> &graph, int cur) {
    int cnt = (tree[cur].empty() ? 1 : 0);
    for (int child : tree[cur]) {
        int child_cnt = build_graph(n, k, is_one, tree, graph, child);
        if (child_cnt % 2 == 1) {
            if (is_one) {
                graph[cur].insert(child);
                graph[child].insert(cur);
            } else {
                int child_node = (child < k ? child : child - k + n);
                graph[cur - k + n].insert(child_node);
                graph[child_node].insert(cur - k + n);
            }
            cnt += child_cnt;
        }
    }
    return cnt;
}

void eulerian_tour(vector<set<int>> &graph, vector<int> &to, int cur) {
    while (!graph[cur].empty()) {
        int next = *graph[cur].begin();
        graph[cur].erase(next);
        graph[next].erase(cur);
        to[cur] = next;
        eulerian_tour(graph, to, next);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> tree1(n);
    vector<bool> leaf(n, true);
    for (int i = 0; i < n - 1; i++) {
        int par;
        cin >> par;
        par--;
        tree1[par].push_back(i);
        leaf[par] = false;
    }
    int k = 0;
    while (leaf[k]) {
        k++;
    }

    vector<vector<int>> tree2(n);
    for (int i = 0; i < m - 1; i++) {
        int par;
        cin >> par;
        par--;
        tree2[par].push_back(i);
    }

    vector<set<int>> graph(n + m - k);
    build_graph(n, k, true, tree1, graph, n - 1);
    build_graph(n, k, false, tree2, graph, m - 1);
    if (graph[n - 1].size() % 2 == 1) {
        graph[n - 1].insert(n + m - k - 1);
        graph[n + m - k - 1].insert(n - 1);
    }

    vector<int> to(n + m - k, -1);
    for (int i = 0; i < n + m - k; i++) {
        if (to[i] == -1) {
            eulerian_tour(graph, to, i);
        }
    }
    for (int i = 0; i < k; i++) {
        if (to[i] < n) {
            cout << "R";
        } else {
            cout << "B";
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3812kb

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
RBR

result:

ok ok (2 test cases)

Test #2:

score: -100
Runtime Error

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: