QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419211#8544. Colorful Graph 2robinyqcWA 160ms3596kbC++201.1kb2024-05-23 18:54:412024-05-23 18:54:55

Judging History

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

  • [2024-05-23 18:54:55]
  • 评测
  • 测评结果:WA
  • 用时:160ms
  • 内存:3596kb
  • [2024-05-23 18:54:41]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
template<typename T> using vec = vector<T>;

void solve()
{
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[i].emplace_back(i + 1);
        g[i + 1].emplace_back(i);
    }
    g[0].emplace_back(n - 1);
    g[n - 1].emplace_back(0);
    while (m--) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vec<char> col(n + 1);
    auto dfs = [&](auto &&f, int x, int fa) -> void
    {
        col[x] = col[fa];
        for (int v: g[x]) if (v != fa) {
            if (col[v]) {
                col[x] = 3 - col[x];
                break;
            }
        }
        for (int v: g[x]) if (!col[v]) f(f, v, x);
    };
    col[n] = 1;
    dfs(dfs, 0, n);
    for (int i = 0; i < n; i++) {
        if (col[i] == 1) cout.put('R');
        else cout.put('B');
    }
    cout << '\n';
}

signed main()
{
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

RRB
RRRB
RRBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 160ms
memory: 3512kb

input:

100000
9 6
2 0
4 6
3 6
0 6
0 7
2 6
3 0
5 2
2 4
2 0
6 3
1 5
4 1
2 4
9 6
3 1
6 4
8 1
3 6
1 6
8 6
3 0
7 4
3 0
4 0
6 4
3 1
7 4
5 1
5 0
3 1
1 4
4 1
1 3
6 3
2 4
4 0
2 0
6 3
3 0
1 3
5 3
7 4
0 5
2 5
5 1
3 5
8 5
4 1
5 1
5 0
1 3
5 7
3 0
8 5
0 2
4 6
0 6
0 3
4 0
8 5
5 1
1 4
5 0
3 1
5 7
3 0
10 7
0 2
9 2
5 8
3 9
...

output:

RRBBBBRBR
RRB
RRBBR
RRRRBR
RRRBBBRRB
RRB
RRRBRRB
RRRBRBR
RRRB
RRBBRB
RRRBBR
RRRRRBR
RRRBRBBR
RRB
RRBRBBRB
RRRBRBBR
RRB
RRBBBBBBRB
RRRBBBRB
RRRRRRRBRB
RRRRRRBRBR
RRBRRRBRRB
RRB
RRRRBBR
RRRBRB
RRBBRBRB
RRRB
RRBBBRB
RRRRRRBRBR
RRRRRBR
RRRRBBRB
RRRBRB
RRBBRB
RRB
RRB
RRRBRRBRB
RRRRBBR
RRRBR
RRRRRBBBRB
RR...

result:

wrong answer cycle detected (test case 4)