QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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)