Submission #1259211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259211		danghuy	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	105 ms	29984 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const ll MAXN=1e5+5,LG=19;
ll n,m,i,j,k,timedfs;
int num[MAXN],low[MAXN],id[MAXN],a[MAXN],b[MAXN],mark[MAXN];
int up[MAXN][20],h[MAXN],par[MAXN],bripar[MAXN];
int goup[MAXN],godown[MAXN],addUp[MAXN],addDown[MAXN];
vector<pair<ll,ll>> adj[MAXN],adj1[MAXN];

void dfs(ll u,int pe){
    num[u]=low[u]=++timedfs;
    for(auto e:adj[u]){
        int v=e.first,idEdge=e.second;
        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(ll u,ll 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.first,idEdge=e.second;
            if(id[v]) continue;
            bool isBridge=0;
            if(num[x]<num[v]&&low[v]>num[x]) isBridge=1;
            if(num[v]<num[x]&&low[x]>num[v]) isBridge=1;
            if(isBridge) continue;
            id[v]=comp; st.push(v);
        }
    }
}

void dfs1(ll u,ll p){
    for(auto e:adj1[u]){
        int v=e.first,idEdge=e.second;
        if(v==p) continue;
        h[v]=h[u]+1;
        par[v]=u; bripar[v]=idEdge;
        up[v][0]=u;
        for(int j=1;j<=LG;j++) up[v][j]=up[ up[v][j-1] ][j-1];
        dfs1(v,u);
    }
}

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

void dfs_acc(int u,int p){
    for(auto e:adj1[u]){
        int v=e.first,idEdge=e.second;
        if(v==p) continue;
        dfs_acc(v,u);
        addUp[u]+=addUp[v];
        addDown[u]+=addDown[v];
        int f=(h[ id[a[idEdge]] ]<h[ id[b[idEdge]] ]?0:1);
        if(addUp[v]>0 && addDown[v]==0) mark[idEdge]=!f;
        else if(addDown[v]>0 && addUp[v]==0) mark[idEdge]=f;
        else mark[idEdge]=2;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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});
    }
    for(i=1;i<=n;i++) if(!num[i]) dfs(i,0);
    int comp=0;
    for(i=1;i<=n;i++) if(!id[i]) dfs_comp(i,++comp);
    for(i=1;i<=m;i++){
        if(id[a[i]]==id[b[i]]) mark[i]=2;
        else{
            bool isBridge=0;
            if(num[a[i]]<num[b[i]]&&low[b[i]]>num[a[i]]) isBridge=1;
            if(num[b[i]]<num[a[i]]&&low[a[i]]>num[b[i]]) isBridge=1;
            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<=comp;i++) if(!h[i]){h[i]=0; up[i][0]=i; dfs1(i,0);}
    cin>>k;
    for(i=1;i<=k;i++){
        int u,v;cin>>u>>v; u=id[u]; v=id[v];
        if(u==v) continue;
        int w=lca(u,v);
        addUp[u]++; addUp[w]--;
        addDown[v]++; addDown[w]--;
    }
    for(i=1;i<=comp;i++) if(par[i]==0) dfs_acc(i,0);
    for(i=1;i<=m;i++){
        if(mark[i]==0) cout<<'R';
        else if(mark[i]==1) cout<<'L';
        else cout<<'B';
    }
    cout<<"\n";
}

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