QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#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;
}

Details

Tip: Click on the bar to expand more detailed information

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)