QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388197#8544. Colorful Graph 2ucup-team135#WA 0ms3632kbC++202.1kb2024-04-13 13:46:072024-04-13 13:46:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-13 13:46:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2024-04-13 13:46:07]
  • 提交

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)