QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611152#8544. Colorful Graph 2ChenJiarun12345WA 0ms14220kbC++141.3kb2024-10-04 19:38:182024-10-04 19:38:18

Judging History

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

  • [2024-10-04 19:38:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14220kb
  • [2024-10-04 19:38:18]
  • 提交

answer

/*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define For(i,l,r) for(register int i=(l);i<=(r);i++)
#define Rof(i,l,r) for(register int i=(l);i>=(r);i--)
#define bug cout<<"Ln:"<<__LINE__<<'\n'
bool MS;
const int N=200005;
int n,m,deg[N],tmp[N],vis[N],col[N],cnt[2];
vector<int>e[N],vec;
void MAIN(int TEST){
	cin>>n>>m;
	For(i,1,n) e[i].clear(),vis[i]=0;
	For(i,1,n) e[i].push_back(i%n+1),e[i%n+1].push_back(i);
	For(i,1,m){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	For(i,1,n) deg[i]=(int)e[i].size();
	For(i,1,n) if(deg[i]<=2) vec.push_back(i);
	Rof(i,n,1){
		if(!(int)vec.size()){
			cout<<"Impossible\n";
			return ;
		}
		int u=vec.back();
		tmp[i]=u,vis[u]=i,vec.pop_back();
		for(int v:e[u]) if(!vis[v]){
			deg[v]--;
			if(deg[v]==2) vec.push_back(v);
		}
	}
	For(i,1,n){
		int u=tmp[i];
		cnt[0]=0,cnt[1]=0;
		for(int v:e[u]) if(vis[v]<vis[u]) cnt[col[v]]++;
		if(cnt[0]<=1) col[u]=0;
		else col[u]=1;
	}
	For(i,1,n) cout<<(!col[i]?"B":"R");
	cout<<'\n';
}
bool MT;
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cerr<<"Memory: "<<1.0*(&MS-&MT)/1048576<<"MiB\n";
	int test=1;
	cin>>test;
	For(TEST,1,test) MAIN(TEST);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14220kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BBR
RBBB
BRBBBR

result:

wrong answer cycle detected (test case 2)