QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402115 | #8544. Colorful Graph 2 | Graphcity | ML | 6ms | 13116kb | C++20 | 1.9kb | 2024-04-29 21:46:34 | 2024-04-29 21:46:35 |
Judging History
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