QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388197 | #8544. Colorful Graph 2 | ucup-team135# | WA | 0ms | 3632kb | C++20 | 2.1kb | 2024-04-13 13:46:07 | 2024-04-13 13:46:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
const int inf=1e18;
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)
{
int n,m;cin>>n>>m;
set<pair<int,int> > h;
for(int i=0;i<m;++i) {int x,y;cin>>x>>y;h.insert({x,y});h.insert({y,x});}
set<int> cur;
for(int i=0;i<2*n;++i) cur.insert(i);
set<pair<int,int> > ears;
auto ear=[&](int x,int y)->bool
{
if(!cur.count(x) || !cur.count(y)) return false;
set<int>::iterator it=cur.find(x);
++it;++it;if(((*it)%n)==y) return true;
it=cur.find(y);
++it;++it;if(((*it)%n)==x) return true;
return false;
};
auto fn=[&](int x,int y)->bool
{
if(!cur.count(x) || !cur.count(y)) return 0;
set<int>::iterator it=cur.find(x);
++it;++it;if(((*it)%n)==y) return (*(--it))%n;
it=cur.find(y);
++it;++it;if(((*it)%n)==x) return (*(--it))%n;
return 0;
};
for(auto [x,y]:h)
{
if(ear(x,y)) {ears.insert({x,y});}
}
vector<array<int,3> > v;
while(cur.size()>4 && !ears.empty())
{
auto o=(*ears.begin());ears.erase(ears.begin());auto [x,y]=o;if(!ear(x,y)) continue;
int z=fn(x,y);
v.app({z,x,y});
}
reverse(all(v));
int ans[n]={0};
int co=0;
for(int i:cur) {if(i<n) {ans[i]=co;co^=1;}}
for(int i=0;i<v.size();++i)
{
int z=v[i][0];int x=v[i][1];int y=v[i][2];
ans[z]=ans[x]^1;
}
for(int i=0;i<n;++i) {cout<<(ans[i] ? 'R' : 'B');}
cout<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3632kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB BBBR BRBRBR
result:
wrong answer cycle detected (test case 3)