QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408870 | #8544. Colorful Graph 2 | daduoli# | WA | 2ms | 5660kb | C++23 | 1.0kb | 2024-05-11 10:04:32 | 2024-05-11 10:04:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read(){
char ch=getchar();
while(!isdigit(ch) && ch!='-') ch=getchar();
int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
return x*ff;
}
const int N=1e6+5;
int n,m,a[N]; char c[N]; vector<int> e[N];
void dfs(int L,int R){ if(L+1==R) return ;
a[m=1]=L;
while(a[m]!=R){
int x=a[m],y=upper_bound(e[x].begin(),e[x].end(),x==L?R-1:R)-e[x].begin()-1;
a[++m]=e[x][y];
} for(int i=2;i<m;i++) c[a[i]]='B';
c[a[2]]=c[a[1]]=='R'?'B':'R';
for(int i=1;i<m;i++) dfs(a[i],a[i+1]);
}
void vmain(){
n=read(); m=read(); c[1]='R'; c[n]='B';
for(int i=1;i<n;i++) e[i].resize(1),e[i][0]=i+1;
e[1].push_back(n);
for(int i=1;i<=m;i++){
int u=read()+1,v=read()+1; if(u>v) swap(u,v);
e[u].push_back(v);
}
for(int i=1;i<n;i++) sort(e[i].begin(),e[i].end());
dfs(1,n);
for(int i=1;i<=n;i++) putchar(c[i]);
puts("");
}
int main(){
int T=read(); while(T--) vmain();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5660kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBB RBRB RBBBBB
result:
wrong answer cycle detected (test case 3)