QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375961 | #8544. Colorful Graph 2 | SolitaryDream# | WA | 82ms | 8544kb | C++17 | 1.4kb | 2024-04-03 18:49:51 | 2024-04-03 18:49:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1e3+7;
int T,n,m;
vector<int> g[N];
int deg[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<n;i++)
g[i].clear();
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=0;i<n;i++)
g[i].push_back((i+1)%n),g[(i+1)%n].push_back(i);
set<pair<int,int> >s;
for(int i=0;i<n;i++)
s.insert({g[i].size(),i});
vector<int> v;
while(s.size())
{
int x=s.begin()->second;
s.erase(s.begin());
v.push_back(x);
deg[x]=0;
for(auto v:g[x])
if(deg[v])
{
s.erase({deg[v],v});
--deg[v];
s.insert({deg[v],v});
}
}
reverse(v.begin(),v.end());
string ans;
ans.resize(n);
for(auto x:v)
{
int c='B';
for(auto y:g[x])
{
if(ans[y]=='B')
c='R';
}
ans[x]=c;
}
cout<<ans<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8276kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RRB RRRB RBRRBR
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 82ms
memory: 8544kb
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:
RBRRRRBRB RRB RRBRR BRRRBR BRBRRRBRR RRB RBRRBRR RBRRRRB RRRB RBRRBR RRRBRR RRRRRBR RRRBRBRR RRB BRRRRBRR RRRBRBRR RRB RBRRRRBRRB BRBRRRBR RRRRRBRRRB BRRRRRBRBR BRRRRBRBRR RRB BRRRBRR RBRRRR RRBRRRRR RRRB RBRRBRB BRBRBRRRRR RRRBRRB RRRRBRRB RBRRRR RBRRBR RRB RRB RBRRRRBRR RRRRBRR RRRBR BRRRRBRRBR RR...
result:
wrong answer cycle detected (test case 18)