QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807936#8544. Colorful Graph 2ucup-team2179#WA 51ms3740kbC++231.2kb2024-12-10 14:52:362024-12-10 14:52:36

Judging History

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

  • [2024-12-10 14:52:36]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:3740kb
  • [2024-12-10 14:52:36]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
vector<int> G[maxn];
int fa[maxn], col[maxn];
int Find(int x) {return fa[x] == x ? fa[x] : fa[x] = Find(fa[x]);}
void dfs(int u, int f) {
    for (auto v : G[u]) {
        if (v == f) continue;
        col[v] = col[u] ^ 1;
        dfs(v, u);
    }
}
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) fa[i] = i, G[i].clear();
    while (m--) {
        int u, v; cin >> u >> v;
        int fu = Find(u), fv = Find(v);
        if (fu == fv) continue;
        fa[fu] = fv;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 0; i < n; i++) {
        int u = i, v = (i + 1) % n;
        int fu = Find(u), fv = Find(v);
        if (fu == fv) continue;
        fa[fu] = fv;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    col[0] = 0;
    dfs(0, 0);
    for (int i = 0; i < n; i++)
        if (col[i]) cout << 'B';
        else cout << 'R';
    cout << "\n";
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

详细

Test #1:

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

input:

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

output:

RBR
RBRR
RBBRRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 51ms
memory: 3628kb

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:

RBBRRBBBR
RBR
RBBRR
RBBRRR
RBRRRBBRR
RBR
RRBBBRR
RRBBBBR
RBRR
RBRBBR
RRBBRR
RRRRBBR
RRBBBBRR
RBR
RBBBRBBR
RRBBBBRR
RBR
RBBBBBBRRR
RBRRBRRR
RBBBBBRRRR
RBBBBRRRRR
RBBBRBBBRR
RBR
RBBRRBR
RBRRRR
RBBRRRRR
RBRR
RBBBRRR
RBBBBRRRRR
RBBBRRR
RBRBBRRR
RBRRRR
RBBRBR
RBR
RBR
RBRRRBBBR
RRRBBRR
RRBBR
RBBBRRBRRR
RR...

result:

wrong answer cycle detected (test case 47)