QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#807936 | #8544. Colorful Graph 2 | ucup-team2179# | WA | 51ms | 3740kb | C++23 | 1.2kb | 2024-12-10 14:52:36 | 2024-12-10 14:52:36 |
Judging History
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)