QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#364955#8130. Yet Another Balanced Coloring Problemchengning0909TL 2ms10636kbC++171.3kb2024-03-24 17:33:242024-03-24 17:33:24

Judging History

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

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

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

result: