QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671589#8544. Colorful Graph 2Ri_Nai#WA 61ms3680kbC++231.4kb2024-10-24 13:34:432024-10-24 13:34:45

Judging History

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

  • [2024-10-24 13:34:45]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:3680kb
  • [2024-10-24 13:34:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (y < x)
            swap(x, y);
        edge[x].push_back(y);
    }
    vector<int> color(n, -1);
    queue<int> Q;
    for (int i = 0; i < n; ++i)
    {
        if (edge[i].empty())
            continue;
        if (color[i] == -1)
        {
            for (int v : edge[i])
                if (color[v] != - 1)
                    color[i] = color[v] ^ 1;
            if (color[i] == -1)
                color[i] = 0;
        }
        for (int v : edge[i])
            color[v] = color[i] ^ 1;
    }
    for (int i = 0; i < n; ++i)
        if (color[i] != -1)
            Q.push(i);
    if (Q.empty())
        Q.push(0), color[0] = 0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        int pre = (u + 1) % n;
        int nxt = (u + n - 1) % n;
        if (color[pre] == -1)
            color[pre] = color[u] ^ 1, Q.push(pre);
        if (color[nxt] == -1)
            color[nxt] = color[u] ^ 1, Q.push(nxt);
    }
    for (int i = 0; i < n; ++i)
        putchar("BR"[color[i]]);
    puts("");
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

BRR
RBRR
BRRBBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 61ms
memory: 3676kb

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:

BRRRRBBRR
BRR
BRRBB
RBBRRR
RBRRRBBRR
BRR
BBRRRBB
BBRRRRR
RBRR
BRRBBR
BBRRBB
BBBBRRR
BBRRRRBB
BRR
BRRRRBBR
BBRRRRBB
BRR
BRRRRRRBBB
RBRRRBBR
RBBBBBRRRR
RBBBBRRRRR
BRRRRBBBRR
BRR
RBBRRBB
RBRRRR
BRRBBBBB
RBRR
BRRRBBB
RBBBBRRRRR
RBBBRRR
RBBRRBBR
RBRRRR
BRRBBR
BRR
BRR
RBRRRBBBR
BBBRRBB
BBRRR
RBBBRRRBBB
BB...

result:

wrong answer cycle detected (test case 83)