QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419022#8544. Colorful Graph 2tarjen#WA 94ms3884kbC++201.1kb2024-05-23 17:02:522024-05-23 17:02:54

Judging History

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

  • [2024-05-23 17:02:54]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:3884kb
  • [2024-05-23 17:02:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
string solve()
{
    int n,m;
    cin>>n>>m;
    set<pair<int,int>> s;
    auto addedge =[&](int x,int y){
        s.insert({x,y});
        s.insert({y,x});
    };
    auto query = [&](int x,int y){
        if(s.find({x,y})!=s.end())return true;
        if(s.find({y,x})!=s.end())return true;
        return false;
    };
    while(m--){
        int x,y;cin>>x>>y;
        addedge(x,y);
    }
    auto pre = [&](int x){
        return (x+n-1)%n;
    };
    auto nxt = [&](int x){
        return (x+1)%n;
    };
    vector<int> ans(n,0);
    int l=0,r=1;
    while((r-l+n)%n!=n-1){
        if(query(pre(l),r)){
            ans[pre(l)]=ans[l]^1;
            l=pre(l);
        }
        else{
            ans[nxt(r)]=ans[r]^1;
            r=nxt(r);
        }
    }
    string st(n,'0');
    for(int i=0;i<n;i++){
        st[i]=ans[i]?'B':'R';
    }
    return st;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

RRB
RRBB
RRBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 94ms
memory: 3884kb

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:

RRBRBRBRB
RRB
RRBRB
RRBRRB
RRBRBRBRB
RRB
RRBRBRB
RRBRBRB
RRBB
RRBRBR
RRBRBB
RRBRBRB
RRBRBRBB
RRB
RRBRBRBR
RRBRBRBB
RRB
RRBRBRBRRB
RRBRBRRB
RRBRBRBBRB
RRBRBRRBRB
RRBRBRBRBB
RRB
RRBRBRB
RRBBRB
RRBRRBRB
RRBB
RRBRBRB
RRBRBRRBRB
RRBRBRB
RRBRBRRB
RRBBRB
RRBRBR
RRB
RRB
RRBRBRBRB
RRBRBRB
RRBRB
RRBRBRBRRB
RR...

result:

wrong answer cycle detected (test case 7)