QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
詳細信息
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)