QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408851 | #8544. Colorful Graph 2 | daduoli# | WA | 76ms | 10512kb | C++14 | 1.4kb | 2024-05-11 09:21:41 | 2024-05-11 09:21:41 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=2e5+10;
int n,m;
int fs[MAXN],pre[MAXN],suf[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
e[f].push_back(t);
}
int sz;
void dfs(int u) {
++sz;
for(auto t:e[u]) {
if(!fs[t]) {
if(fs[u]==1) fs[t]=2;
else fs[t]=1;
dfs(t);
}
}
}
void vmain() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
e[i].clear();
fs[i]=0;
}
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
++u; ++v;
add(u,v);
add(v,u);
}
int lr=0,lb=0;
for(int i=1;i<=n;++i) {
if(!fs[i]) {
fs[i]=1; sz=0;
dfs(i);
if(sz==1) fs[i]=0;
}
}
if(!m) {
for(int i=1;i<=n;++i) {
if((i&1)) printf("R");
else printf("B");
}
puts("");
return ;
}
int pp=0,ss=0;
for(int i=1;i<=n;++i) {
if(fs[i]) {
ss=i;
break;
}
}
for(int i=n;i>=1;--i) {
if(fs[i]) {
pp=i;
break;
}
}
for(int i=1;i<=n;++i) {
if(fs[i]) pp=i;
pre[i]=pp;
}
for(int i=n;i>=1;--i) {
if(fs[i]) ss=i;
suf[i]=ss;
}
for(int i=1;i<=n;++i) {
if(!fs[i]) {
// if(i==n) {
// cout<<pre[i]<<" "<<suf[i]<<endl;
// }
if(fs[pre[i]]==fs[suf[i]]) {
if(fs[pre[i]]==1) fs[i]=2;
else fs[i]=1;
}
else fs[i]=1;
}
}
for(int i=1;i<=n;++i) {
if(fs[i]==1) printf("R");
else printf("B");
} puts("");
}
int main () {
int T;
scanf("%d",&T);
while(T--) vmain();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10512kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBR RRRB RRBRRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 76ms
memory: 9536kb
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:
RRBBBRRBR RBR RRBRR RRRRBB RRRBBRRRB RBR RRRBBRR RRRBBBR RRRB RBRRBR RRRBRR RRRRRBR RRRBBBRR RBR RRBBRRBR RRRBBBRR RBR RRBBBBBRRR RRBRRRBB RRRRRRRBBB RRRRRRBBBB RRBBRRBBRR RBR RRBRRRB RRRBBB RRBRRRRR RRRB RRBBRRR RRRRRRBBBB RRRRRBB RRBRRRBB RRRBBB RRBRRB RBR RBR RRRBBRRRB RRRRBRR RRRBR BRRRRBBRRR RR...
result:
wrong answer cycle detected (test case 47)