QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578565 | #8544. Colorful Graph 2 | gungod | TL | 7ms | 50932kb | C++14 | 1.2kb | 2024-09-20 20:03:10 | 2024-09-20 20:03:10 |
Judging History
answer
#pragma Optimize(Ofast)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (l+r>>1)
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
const int N=1e6+10;
int n,a[N],col[N],m;
set<int>G[N];
void solve(int s) {
if(!G[s].size()) return ;
int p=s,las=s;
bool vis[3]={0,0,0};
vector<int>r;
do{
int q=*G[p].rbegin()%n;
if(q==las) {
auto it=G[p].rbegin();it++;
if(it==G[p].rend()) return ;
q=*it%n;
}
las=p;
r.push_back(q);
p=q;//cout<<p<<" ";
vis[col[p]]=1;
}while(p!=s);//puts("f");
for(int i=0;i<r.size();i++) {
p=r[i];
if(!col[p]) {
if(vis[2]) col[p]=1;
else col[p]=2,vis[2]=1;
}
}
p=s;
for(int i=0;i<r.size();i++) {
G[p].erase(r[i]+(r[i]==0)*n);//cout<<p<<" "<<r[i]<<endl;
p=r[i];
}
for(auto u:r) {
solve(u);
}
}
void main1() {
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) G[i].clear(),col[i]=0;
for(int i=0;i<n;i++) G[i].insert(i+1);
for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),G[u].insert(v+(v==0)*n),G[v].insert((u==0)*n+u);
solve(0);
for(int i=0;i<n;i++) if(col[i]==1) putchar('B');else putchar('R');
puts("");
}
int T;
int main() {
scanf("%d",&T);
while(T--) main1();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 50932kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB BRBB BRBBRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Time 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 ...