QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388207#8544. Colorful Graph 2ucup-team135#WA 220ms3872kbC++202.2kb2024-04-13 13:51:282024-04-13 13:51:30

Judging History

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

  • [2024-04-13 13:51:30]
  • 评测
  • 测评结果:WA
  • 用时:220ms
  • 内存:3872kb
  • [2024-04-13 13:51:28]
  • 提交

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)->int
        {
            if(!cur.count(x) || !cur.count(y)) return 0;
            set<int>::iterator it=cur.find(x);
            ++it;++it;if(((*it)%n)==y) {--it;return (*it)%n;}
            it=cur.find(y);
            ++it;++it;if(((*it)%n)==x) {--it;debug((*it),n);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);debug(z);cur.erase(z);cur.erase(z+n);
            debug(z,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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BRB
BBRR
BRBRRR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 220ms
memory: 3872kb

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:

BRRBRBBRR
BRB
BRBRR
RBRBBR
RBRRBRRBB
BRB
BRBBRBB
BRBBRBR
BBRR
BRBRRR
BRBBRR
BRBRBBR
BRBBRBRR
BRB
BRRBRBBR
BRBBRBRR
BRB
BRRBRBRBBR
RBRRBRRB
RBRBRBRRBR
RBRBRBBRBR
BRRBRBBRBB
BRB
RBRBBRR
RBRRBR
BRRBBRBR
BBRR
BRRBRRB
RBRBRBBRBR
RBRBRRB
RBRBBRRB
RBRRBR
BRBRRR
BRB
BRB
RBRRBRRBR
BRBRRBB
BBRRR
RBRBRRBRRB
BB...

result:

wrong answer cycle detected (test case 22)