Submission #1226870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226870		lukasuliashvili	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	6 ms	11584 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<pair<int,int>>g[N];
int tin[N],low[N],tmr;
bool br[N];
int c[N],ccnt;
vector<int>tr[N];
int p[N][17],dep[N];
map<pair<int,int>,int>bidx;
struct E{int u,v;}e[N];
int edir[N];
void dfsb(int v,int pa=-1,int pi=-1){
    tin[v]=low[v]=++tmr;
    for(auto[to,i]:g[v]){
        if(to==pa&&i==pi)continue;
        if(tin[to])low[v]=min(low[v],tin[to]);
        else{
            dfsb(to,v,i);
            low[v]=min(low[v],low[to]);
            if(low[to]>tin[v])br[i]=1;
        }
    }
}
void dfsc(int u,int cc){
    c[u]=cc;
    for(auto[v,i]:g[u])
        if(c[v]==-1&&!br[i])dfsc(v,cc);
}
void dfslca(int u,int pa){
    p[u][0]=pa;
    for(int i=1;i<17;i++)
        if(p[u][i-1]!=-1)p[u][i]=p[p[u][i-1]][i-1];
    for(int v:tr[u])
        if(v!=pa){dep[v]=dep[u]+1;dfslca(v,u);}
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=16;i>=0;i--)
        if(p[u][i]!=-1&&dep[p[u][i]]>=dep[v])u=p[u][i];
    if(u==v)return u;
    for(int i=16;i>=0;i--)
        if(p[u][i]!=-1&&p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];
    return p[u][0];
}
void mark(int u,int v,int up){
    while(u!=v){
        int pa=p[u][0],a=u,b=pa;
        if(a>b)swap(a,b);
        int idx=bidx[{a,b}];
        if(up)edir[idx]|=1;
        else edir[idx]|=2;
        u=pa;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;u--;v--;
        g[u].emplace_back(v,i);
        g[v].emplace_back(u,i);
        e[i]={u,v};
    }
    dfsb(0);
    fill(c,c+n,-1);
    ccnt=0;
    for(int i=0;i<n;i++)
        if(c[i]==-1)dfsc(i,ccnt++);
    int id=0;
    for(int i=0;i<m;i++){
        if(br[i]){
            int a=c[e[i].u],b=c[e[i].v];
            tr[a].push_back(b);
            tr[b].push_back(a);
            int x=min(a,b),y=max(a,b);
            bidx[{x,y}]=id++;
        }
    }
    memset(p,-1,sizeof p);
    dfslca(0,-1);
    int q;cin>>q;
    while(q--){
        int u,v;cin>>u>>v;u--;v--;
        u=c[u];v=c[v];
        int w=lca(u,v);
        mark(u,w,1);
        mark(v,w,0);
    }
    string res;
    for(int i=0;i<m;i++){
        if(!br[i])res+='B';
        else{
            int a=c[e[i].u],b=c[e[i].v];
            int x=min(a,b),y=max(a,b);
            int idx=bidx[{x,y}];
            int cu=c[e[i].u],cv=c[e[i].v];
            if(edir[idx]==1){
                if(cu==x&&cv==y)res+='R';
                else res+='L';
            }else if(edir[idx]==2){
                if(cu==x&&cv==y)res+='L';
                else res+='R';
            }else res+='B';
        }
    }
    cout<<res<<'\n';
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40