QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#554183 | #8544. Colorful Graph 2 | ucup-team1231# | WA | 0ms | 8728kb | C++14 | 1.3kb | 2024-09-09 08:19:40 | 2024-09-09 08:19:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m, deg[200005];
bool vis[200005];
vector<int> G[200005];
void adde(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
char S[200005];
void solve() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 0; i < n; i++) adde(i % n + 1, (i + 1) % n + 1);
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> que;
for(int i = 1; i <= n; i++) if((deg[i] = G[i].size()) <= 2) {
que.push(i); vis[i] = true;
} else vis[i] = false;
vector<int> seq;
while(!que.empty()) {
int v = que.front(); que.pop();
seq.push_back(v);
for(auto u : G[v]) if(!vis[u]) {
deg[u]--;
if(deg[u] <= 2) {
vis[u] = true; que.push(u);
}
}
}
reverse(seq.begin(), seq.end());
for(int i = 1; i <= n; i++) S[i] = ' ';
for(auto v : seq) {
for(auto u : G[v]) if(S[u] != ' ') S[v] = S[u] == 'R' ? 'B' : 'R';
if(S[v] == ' ') S[v] = 'R';
}
printf("%s\n", S + 1);
}
int main() {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8728kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BBR BBRR BBBRBR
result:
wrong answer cycle detected (test case 3)