Submission #1259206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259206		danghuy	One-Way Streets (CEOI17_oneway)	C++20	60 / 100	3097 ms	33236 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define si size()
#define fi first
#define se second
#define ll int
#define sr sort
#define pb push_back
const ll MAXN=1e5+5,MOD=1e6,LG=19;
ll n,m,j,k,p,i,f,dem,ans,t,l,r=1,timedfs;
int id[MAXN], num[MAXN], low[MAXN], mark[MAXN], a[MAXN], b[MAXN];
int up[MAXN][20], goup[MAXN], godown[MAXN], h[MAXN], par[MAXN], bripar[MAXN];
string s,s1;
stack<ll> scc;
vector<pair<ll,ll>> adj[MAXN], adj1[MAXN];
map<pair<ll,ll>,ll> ma;

void dfs(ll u, int pe){
    num[u]=low[u]=++timedfs;
    for(auto e: adj[u]){
        int v=e.fi, idedge=e.se;
        if(idedge==pe) continue;
        if(!num[v]){
            dfs(v, idedge);
            low[u]=min(low[u], low[v]);
        } else {
            low[u]=min(low[u], num[v]);
        }
    }
}

void dfs_comp(int u, int comp){
    stack<int> st; st.push(u); id[u]=comp;
    while(!st.empty()){
        int x=st.top(); st.pop();
        for(auto e: adj[x]){
            int v=e.fi, idedge=e.se;
            if(id[v]) continue;
            bool isBridge = false;
            if(num[x] < num[v] && low[v] > num[x]) isBridge = true;
            if(num[v] < num[x] && low[x] > num[v]) isBridge = true;
            if(isBridge) continue;
            id[v]=comp; st.push(v);
        }
    }
}

void dfs1(ll st, ll pre){
    for(auto x:adj1[st]){
        if(x.fi==pre) continue;
        h[x.fi]=h[st]+1;
        up[x.fi][0]=st;
        par[x.fi]=st;
        bripar[x.fi]=x.se;
        for(ll j=1;j<=LG;j++)
            up[x.fi][j]=up[ up[x.fi][j-1] ][j-1];
        dfs1(x.fi,st);
    }
}

ll lca(ll u,ll v){
    if(u==0||v==0) return 0;
    if(h[u]!=h[v]){
        if(h[u]<h[v]) swap(u,v);
        ll cnt=h[u]-h[v];
        for(ll j=0;j<=LG;j++)
            if((cnt>>j)&1) u=up[u][j];
    }
    if(u==v) return u;
    for(ll j=LG;j>=0;j--)
        if(up[u][j]!=up[v][j])
            u=up[u][j],v=up[v][j];
    return up[u][0];
}

void go(ll st,ll en,ll type){
    while(st!=en){
        if(type==1) goup[ bripar[st] ] = 1;
        else godown[ bripar[st] ] = 1;
        st=par[st];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        a[i]=u; b[i]=v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        pair<int,int> pr = {min(u,v), max(u,v)};
        ma[pr]++;
    }
    for(i=1;i<=n;i++){
        num[i]=low[i]=0;
        id[i]=0;
    }
    timedfs=0;
    for(i=1;i<=n;i++){
        if(!num[i]) dfs(i, 0);
    }
    int compcnt=0;
    for(i=1;i<=n;i++){
        if(!id[i]){
            ++compcnt;
            dfs_comp(i, compcnt);
        }
    }
    for(i=1;i<=m;i++){
        if(id[a[i]]==id[b[i]] || ma[{min(a[i],b[i]), max(a[i],b[i])}]>1){
            mark[i]=2;
        } else {
            bool isBridge = false;
            if(num[a[i]] < num[b[i]] && low[b[i]] > num[a[i]]) isBridge = true;
            if(num[b[i]] < num[a[i]] && low[a[i]] > num[b[i]]) isBridge = true;
            if(isBridge){
                adj1[ id[a[i]] ].pb({ id[b[i]], i });
                adj1[ id[b[i]] ].pb({ id[a[i]], i });
            } else mark[i]=2;
        }
    }
    for(i=1;i<=compcnt;i++){
        h[i]=0;
        par[i]=0;
        bripar[i]=0;
        for(j=0;j<=LG;j++) up[i][j]=0;
    }
    for(i=1;i<=compcnt;i++){
        if(up[i][0]==0){
            up[i][0]=i;
            h[i]=0;
            dfs1(i,i);
        }
    }
    cin>>k;
    for(i=1;i<=k;i++){
        int u,v; cin>>u>>v;
        u = id[u]; v = id[v];
        if(u==0 || v==0) continue;
        ll kk = lca(u,v);
        if(kk==0) continue;
        go(u,kk,1);
        go(v,kk,-1);
    }
    for(i=1;i<=m;i++){
        if(mark[i]==0){
            int f = ( h[ id[a[i]] ] < h[ id[b[i]] ] ? 0 : 1 );
            if(goup[i]) mark[i]=!f;
            else if(godown[i]) mark[i]=f;
            else mark[i]=2;
        }
    }
    for(i=1;i<=m;i++){
        if(mark[i]==0) cout<<'R';
        else if(mark[i]==1) cout<<'L';
        else cout<<'B';
    }
    cout<<"\n";
    return 0;
}

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