QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
详细
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)