QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375961#8544. Colorful Graph 2SolitaryDream#WA 82ms8544kbC++171.4kb2024-04-03 18:49:512024-04-03 18:49:52

Judging History

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

  • [2024-04-03 18:49:52]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:8544kb
  • [2024-04-03 18:49:51]
  • 提交

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);
            deg[x]=0;
            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: 0ms
memory: 8276kb

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: 82ms
memory: 8544kb

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)