QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578565#8544. Colorful Graph 2gungodTL 7ms50932kbC++141.2kb2024-09-20 20:03:102024-09-20 20:03:10

Judging History

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

  • [2024-09-20 20:03:10]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:50932kb
  • [2024-09-20 20:03:10]
  • 提交

answer

#pragma Optimize(Ofast)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (l+r>>1)
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
const int N=1e6+10;
int n,a[N],col[N],m;
set<int>G[N];
void solve(int s) {
	if(!G[s].size()) return ;
	int p=s,las=s;
	bool vis[3]={0,0,0};
	vector<int>r;
	do{
		int q=*G[p].rbegin()%n;
		if(q==las) {
			auto it=G[p].rbegin();it++;
			if(it==G[p].rend()) return ;
			q=*it%n;
		}
		las=p;
		r.push_back(q);
		p=q;//cout<<p<<" ";
		vis[col[p]]=1;
	}while(p!=s);//puts("f");
	for(int i=0;i<r.size();i++) {
		p=r[i];
		if(!col[p]) {
			if(vis[2]) col[p]=1;
			else col[p]=2,vis[2]=1;
		}
	}
	p=s;
	for(int i=0;i<r.size();i++) {
		G[p].erase(r[i]+(r[i]==0)*n);//cout<<p<<" "<<r[i]<<endl;
		p=r[i];
	}
	for(auto u:r) {
		solve(u);
	}
}
void main1() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) G[i].clear(),col[i]=0;
	for(int i=0;i<n;i++) G[i].insert(i+1);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),G[u].insert(v+(v==0)*n),G[v].insert((u==0)*n+u);
	solve(0);
	for(int i=0;i<n;i++) if(col[i]==1) putchar('B');else putchar('R');
	puts("");
}
int T;
int main() {
	scanf("%d",&T);
	while(T--) main1();
	
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 50932kb

input:

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

output:

BRB
BRBB
BRBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Time Limit Exceeded

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:


result: