QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611387 | #8544. Colorful Graph 2 | junee | WA | 113ms | 14060kb | C++14 | 1.4kb | 2024-10-04 20:47:43 | 2024-10-04 20:47:45 |
Judging History
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)