QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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";
    }
}

详细

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)