QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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();
    }
}

詳細信息

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)