QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611387#8544. Colorful Graph 2juneeWA 113ms14060kbC++141.4kb2024-10-04 20:47:432024-10-04 20:47:45

Judging History

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

  • [2024-10-04 20:47:45]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:14060kb
  • [2024-10-04 20:47:43]
  • 提交

answer

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
#include<queue>
#include<vector>
#include<unordered_map>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=2e5+10;
int T,n,m;
int d[N];
int c[N];
queue<int>q;
vector<unordered_map<int,int>>mp(N); // 修改为 vector

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		// 初始化
		for(int i=1;i<=n;i++){
			c[i]=0;
			mp[i].clear(); // 清空 mp[i]
			if(i!=n)mp[i].insert({i+1,i+1});
			else mp[i].insert({1,1});
			if(i!=1)mp[i].insert({i-1,i-1});
			else mp[i].insert({n,n});
		}
		for(int i=1,x,y;i<=m;i++){
			cin>>x>>y;
			x++,y++; // 确认这部分是否需要
			mp[x].insert({y,y});
			mp[y].insert({x,x});
		}
		// 队列清空
		q = queue<int>();  // 重置队列
		for(int i=1;i<=n;i++){
			if(mp[i].size()==2)q.push(i);
		}
		while(q.size()){
			int u=q.front();
			q.pop();
			int c1=-1,c2=-1;
			for(auto i:mp[u]){
				mp[i.second].erase(u);
				if(mp[i.second].size()==2)
					q.push(i.second);
				if(c1==-1)c1=c[i.second];
				else if(c2==-1)c2=c[i.second];
			}
			if(c1!=-1 && c1==c2) c[u]=c1^1; // 增加检查条件
		}
		for(int i=1;i<=n;i++){
			if(c[i])cout<<"R";
			else cout<<'B';
		}
		cout<<'\n';
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14060kb

input:

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

output:

RBB
RBRB
BRRRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 113ms
memory: 14024kb

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:

RRBRRRBRR
RBB
RRBRB
RBRRBR
RBRRRRBRR
RBB
BRRRBRR
RBRRRBR
RBRB
BRRRBR
BRRBRR
RBRRRBR
RBRRRBRR
RBB
BRRRBRRR
RBRRRBRR
RBB
RRRRBRRRRB
RRRBRRBR
RRRBRRRRBR
RRBRRRRBRR
RRRBRRRBRR
RBB
RBRRBRR
RBRRBR
RRBRRRBR
RBRB
RRRBRRB
RRBRRRRBRR
RRBRRBR
RBRRBRRR
RBRRBR
BRRRBR
RBB
RBB
RRRRBRRBR
BRRRBRR
BRRBR
RRRRRBRRRB
BR...

result:

wrong answer cycle detected (test case 1)