Submission #1226874

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

oneway

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

const int N=100123, LOG=18;

int n,m,q;
int h[N], low[N], timer;
bool isBridge[N], vis[N];
int comp[N], compCnt;
int par[LOG][N], dep[N];
int man[N], mos[N];

struct Edge {
    int to,id,nxt;
};

Edge edges[2*N];
int head[N], edge_cnt;

int uE[N], vE[N];
int ans[N];

void add_edge(int u,int v,int id){
    edges[++edge_cnt] = {v,id,head[u]};
    head[u] = edge_cnt;
    edges[++edge_cnt] = {u,id,head[v]};
    head[v] = edge_cnt;
}

void find_bridges(int v,int p,int pId){
    vis[v]=true;
    h[v] = p == -1 ? 0 : h[p] + 1;
    low[v] = h[v];
    for(int i=head[v]; i; i=edges[i].nxt){
        int to=edges[i].to, idx=edges[i].id;
        if(idx == pId) continue;
        if(!vis[to]){
            find_bridges(to,v,idx);
            low[v] = min(low[v], low[to]);
            if(low[to] > h[v]) isBridge[idx] = true;
        }else if(to != p){
            low[v] = min(low[v], h[to]);
        }
    }
}

void dfs_comp(int v){
    comp[v] = compCnt;
    for(int i=head[v]; i; i=edges[i].nxt){
        int to=edges[i].to;
        if(comp[to] == -1 && !isBridge[edges[i].id]){
            dfs_comp(to);
        }
    }
}

void dfs_lca_prep(int v,int p){
    vis[v] = true;
    par[0][v] = p;
    for(int i=1; i<LOG; i++){
        if(par[i-1][v] == -1) par[i][v] = -1;
        else par[i][v] = par[i-1][par[i-1][v]];
    }
    for(int i=head[v]; i; i=edges[i].nxt){
        int to=edges[i].to;
        if(to != p && !vis[to]){
            dep[to] = dep[v] + 1;
            dfs_lca_prep(to,v);
        }
    }
    man[v] = mos[v] = 1e9;
}

int jump(int v,int d){
    for(int i=0; i<LOG; i++) if(d & (1<<i)) v = par[i][v];
    return v;
}

int lca(int u,int v){
    if(dep[u] < dep[v]) swap(u,v);
    u = jump(u, dep[u]-dep[v]);
    if(u == v) return u;
    for(int i=LOG-1; i>=0; i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

void dfs_propagate(int v,int p,int id=0){
    vis[v] = true;
    for(int i=head[v]; i; i=edges[i].nxt){
        int to=edges[i].to, idx=edges[i].id;
        if(to != p && !vis[to]){
            dfs_propagate(to,v,idx);
            man[v] = min(man[v], man[to]);
            mos[v] = min(mos[v], mos[to]);
        }
    }
    if(id){
        int a = comp[uE[id]], b = comp[vE[id]];
        if(man[v] != 1e9) ans[id] = (a == p ? 1 : 2);
        else if(mos[v] != 1e9) ans[id] = (a == p ? 2 : 1);
        else ans[id] = 0;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    edge_cnt = 0;
    memset(head,0,sizeof(head));
    for(int i=1; i<=m; i++){
        int a,b; cin >> a >> b;
        uE[i] = a; vE[i] = b;
        add_edge(a,b,i);
        isBridge[i] = false;
        ans[i] = 0;
    }

    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++){
        if(!vis[i]) find_bridges(i,-1,-1);
    }

    // Build components by contracting non-bridge edges
    memset(comp,-1,sizeof(comp));
    compCnt = 0;
    memset(head,0,sizeof(head));
    edge_cnt = 0;

    // Add only non-bridge edges for components
    for(int i=1; i<=m; i++){
        if(!isBridge[i]){
            add_edge(uE[i], vE[i], i);
            add_edge(vE[i], uE[i], i); // added for undirected DFS
        }
    }

    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++){
        if(comp[i] == -1){
            compCnt++;
            dfs_comp(i);
        }
    }

    // Build bridge tree with components as nodes
    memset(head,0,sizeof(head));
    edge_cnt = 0;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=compCnt; i++){
        man[i] = mos[i] = 1e9;
    }
    for(int i=1; i<=m; i++){
        if(isBridge[i]){
            int a = comp[uE[i]], b = comp[vE[i]];
            add_edge(a,b,i);
        }
    }

    // Prepare LCA on bridge tree
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=compCnt; i++){
        if(!vis[i]){
            dep[i] = 0;
            dfs_lca_prep(i, -1);
        }
    }

    cin >> q;
    for(int i=0; i<q; i++){
        int a,b; cin >> a >> b;
        a = comp[a]; b = comp[b];
        if(a == b) continue;
        int w = lca(a,b);
        man[b] = min(man[b], dep[w]);
        mos[a] = min(mos[a], dep[w]);
    }

    memset(vis,0,sizeof(vis));
    for(int i=1; i<=compCnt; i++){
        if(!vis[i]){
            dfs_propagate(i, -1);
        }
    }

    // Output final directions
    for(int i=1; i<=m; i++){
        if(!isBridge[i]) cout << 'B';
        else if(ans[i] == 1) cout << 'R';
        else if(ans[i] == 2) cout << 'L';
        else cout << 'B';
    }
    cout << '\n';
    return 0;
}

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