QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402115#8544. Colorful Graph 2GraphcityML 6ms13116kbC++201.9kb2024-04-29 21:46:342024-04-29 21:46:35

Judging History

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

  • [2024-04-29 21:46:35]
  • 评测
  • 测评结果:ML
  • 用时:6ms
  • 内存:13116kb
  • [2024-04-29 21:46:34]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;

int n,m,fa[Maxn+5],id[Maxn+5],col[Maxn+5];
vector<int> w[Maxn+5],qr[Maxn+5],v[Maxn+5];
map<int,int> mp[Maxn+5];
inline int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline void Addedge(int a,int b) {v[a].push_back(b),v[b].push_back(a);}
inline void dfs(int x,int fa)
{
    int c0=0,c1=0;
    for(auto i:w[x]) if(col[i]!=-1) (col[i]?c1:c0)++;
    for(auto i:w[x]) if(col[i]==-1)
        {if(c0<=c1) col[i]=0,c0++; else col[i]=1,c1++;}
    for(auto y:v[x]) if(y!=fa) dfs(y,x);
}
inline void Solve()
{
    cin>>n>>m; For(i,1,n+1) fa[i]=i,col[i]=-1;
    For(i,1,m)
    {
        int a,b; cin>>a>>b; a++,b++; if(a>b) swap(a,b);
        qr[b].push_back(a);
    }
    For(i,1,n) sort(qr[i].begin(),qr[i].end(),greater<int>());
    int cur=0; For(i,1,n) for(auto j:qr[i])
    {
        ++cur; for(int k=Find(j+1);k<i;k=fa[k])
            w[cur].push_back(k),fa[k]=Find(k+1);
        w[cur].push_back(i),w[cur].push_back(j);
    }
    ++cur; for(int k=Find(1);k<=n;k=fa[k])
        w[cur].push_back(k),fa[k]=Find(k+1);
    For(i,1,m+1) sort(w[i].begin(),w[i].end(),greater<int>());
    iota(id+1,id+m+2,1);
    sort(id+1,id+m+2,[&](int a,int b){return w[a]<w[b];});
    For(i,1,m+1)
    {
        int sz=w[i].size(); For(j,0,sz-1)
        {
            int b=w[i][j],a=w[i][(j+1)%sz];
            if(b==a%n+1) continue; if(a>b) swap(a,b);
            if(!mp[a][b]) mp[a][b]=i; else Addedge(i,mp[a][b]);
        }
    } dfs(1,0);
    For(i,1,n) putchar(col[i]?'R':'B'); printf("\n");
    For(i,1,m) vector<int>().swap(w[i]),vector<int>().swap(v[i]);
    For(i,1,n) vector<int>().swap(qr[i]),mp[i].clear();
}

int main()
{
    // freopen("1.in","r",stdin);

    int T; cin>>T;
    while(T--) Solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 13116kb

input:

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

output:

BRB
RBRB
BRBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Memory Limit Exceeded

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:

BRBBBBRBR
BRB
BRBBR

result: