Submission #619522

#	Time	Username	Problem	Language	Result	Execution time	Memory
619522		czhang2718	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	243 ms	35512 KiB

oneway

#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define sz(x) int(x.size())

const int N=1e5+1, K=18;
int n, m, q;
vector<int> adj[N], adj2[N];
int edge[N][2];
bool vis[N];
bool bridge[N];
int par[N];
set<int> s[N];
char dir[N];
int p[N][K];
int h[N];

void dfs(int x, int prv){
    // e = prv edge
    vis[x]=1;
    for(int e:adj[x]){
        if(e==prv) continue;
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) s[x].insert(k);
    }
    for(int e:adj[x]){
        if(e==prv) continue;
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        dfs(k, e);
        if(sz(s[k])>sz(s[x])) swap(s[x], s[k]);
        for(int u:s[k]) s[x].insert(u);
    }
    s[x].erase(x);
    // cout << "s[" << x << "]\n";
    // for(int t:s[x]) cout << t << " ";
    //     cout << "\n";
    if(!sz(s[x]) && prv) bridge[prv]=1;
}

int find(int x){ return par[x]==x?x:par[x]=find(par[x]); }
void join(int x, int y){ par[find(x)]=find(y); }

void dfs2(int x){
    vis[x]=1;
    for(int e:adj[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(!bridge[e] && !vis[k]){
            join(x,k);
            dfs2(k);
        }
    }
}

void dfs3(int x){
    vis[x]=1;
    rep(i,1,K-1) p[x][i]=p[p[x][i-1]][i-1];
    for(int e:adj2[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        h[k]=h[x]+1;
        p[k][0]=x;
        // cout << "par " << k << " " << x << "\n";
        dfs3(k);
    }
}

int up[N], down[N];

void dfs4(int x, int prv){
    vis[x]=1;
    for(int e:adj2[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        p[k][0]=x;
        dfs4(k, e);
        up[x]+=up[k];
        down[x]+=down[k];
    }
    assert(!(up[x] && down[x]));
    if(prv){
        if(up[x]) dir[prv]=edge[prv][0]==x?'R':'L';
        if(down[x]) dir[prv]=edge[prv][1]==x?'R':'L';
    }
}

int lca(int u, int v){
    if(h[v]>h[u]) swap(u,v);
    int d=h[u]-h[v];
    rep(k,0,K-1){
        if(d&(1<<k)) u=p[u][k];
    }
    if(u==v) return u;
    for(int k=K-1; k>=0; k--){
        if(p[u][k] && p[u][k]!=p[v][k]){
            u=p[u][k];
            v=p[v][k];
        }
    }
    return p[u][0];
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    rep(i,1,m){
        int u,v; cin >> u >> v;
        if(u==v){
            dir[i]='B'; continue;
        }
        edge[i][0]=u;
        edge[i][1]=v;
        dir[i]='B';
        adj[u].push_back(i);
        adj[v].push_back(i);
    }

    rep(i,1,n){
        par[i]=i;
        if(vis[i]) continue;
        dfs(i, 0);
    }
    rep(i,1,n) vis[i]=0;

    rep(i,1,n){
        if(vis[i]) continue;
        dfs2(i);
    }

    rep(e,1,m){
        // if(bridge[e]) cout << "bridge " << e << '\n';
        int a=find(edge[e][0]);
        int b=find(edge[e][1]);
        edge[e][0]=a;
        edge[e][1]=b;
        if(a!=b) adj2[a].push_back(e), adj2[b].push_back(e);
    }

    rep(i,1,n) vis[i]=0;
    rep(i,1,n){
        if(vis[i]) continue;
        dfs3(i);
    }

    cin >> q;
    while(q--){
        int u,v; cin >> u >> v;
        u=find(u);
        v=find(v);
        if(u==v) continue;
        int a=lca(u,v);
        up[u]++;
        up[a]--;
        down[v]++;
        down[a]--;
        // cout << u << " " << a << " " << v << "\n";
    }

    rep(i,1,n) vis[i]=0;
    rep(i,1,n){
        if(!vis[i]) dfs4(i, 0);
    }

    rep(i,1,m) cout << dir[i];
}
// find bridges
// tree

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