QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408870#8544. Colorful Graph 2daduoli#WA 2ms5660kbC++231.0kb2024-05-11 10:04:322024-05-11 10:04:33

Judging History

你现在查看的是最新测评结果

  • [2024-05-11 10:04:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5660kb
  • [2024-05-11 10:04:32]
  • 提交

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)