QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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)