QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419211 | #8544. Colorful Graph 2 | robinyqc | WA | 160ms | 3596kb | C++20 | 1.1kb | 2024-05-23 18:54:41 | 2024-05-23 18:54:55 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T> using vec = vector<T>;
void solve()
{
int n, m;
cin >> n >> m;
vec<vec<int>> g(n);
for (int i = 0; i < n - 1; i++) {
g[i].emplace_back(i + 1);
g[i + 1].emplace_back(i);
}
g[0].emplace_back(n - 1);
g[n - 1].emplace_back(0);
while (m--) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vec<char> col(n + 1);
auto dfs = [&](auto &&f, int x, int fa) -> void
{
col[x] = col[fa];
for (int v: g[x]) if (v != fa) {
if (col[v]) {
col[x] = 3 - col[x];
break;
}
}
for (int v: g[x]) if (!col[v]) f(f, v, x);
};
col[n] = 1;
dfs(dfs, 0, n);
for (int i = 0; i < n; i++) {
if (col[i] == 1) cout.put('R');
else cout.put('B');
}
cout << '\n';
}
signed main()
{
int t;
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: 3596kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RRB RRRB RRBBRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 160ms
memory: 3512kb
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:
RRBBBBRBR RRB RRBBR RRRRBR RRRBBBRRB RRB RRRBRRB RRRBRBR RRRB RRBBRB RRRBBR RRRRRBR RRRBRBBR RRB RRBRBBRB RRRBRBBR RRB RRBBBBBBRB RRRBBBRB RRRRRRRBRB RRRRRRBRBR RRBRRRBRRB RRB RRRRBBR RRRBRB RRBBRBRB RRRB RRBBBRB RRRRRRBRBR RRRRRBR RRRRBBRB RRRBRB RRBBRB RRB RRB RRRBRRBRB RRRRBBR RRRBR RRRRRBBBRB RR...
result:
wrong answer cycle detected (test case 4)