QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375959 | #8544. Colorful Graph 2 | SolitaryDream# | WA | 75ms | 8556kb | C++17 | 1.3kb | 2024-04-03 18:48:57 | 2024-04-03 18:48:58 |
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);
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: 1ms
memory: 8544kb
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: 75ms
memory: 8556kb
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)