제출 #994470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
994470		vladilius	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

struct TR{
    vector<vector<int>> g;
    vector<pii> ed;
    int n;
    TR(int ns){
        n = ns;
        g.resize(n + 1);
    }
    void add(int u, int v){
        ed.pb({u, v});
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> sz, h, p, d;
    void fill(int v, int pr){
        p[v] = pr;
        sz[v] = 1;
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
            if (sz[i] > sz[h[v]]){
                h[v] = i;
            }
            sz[v] += sz[i];
        }
    }
    vector<int> hd, pos;
    int cnt;
    void fill_hld(int v, int k){
        pos[v] = ++cnt;
        hd[v] = k;
        if (!h[v]) return;
        fill_hld(h[v], k);
        for (int i: g[v]){
            if (i != p[v] && i != h[v]){
                fill_hld(i, i);
            }
        }
    }
    vector<int> f, inv;
    vector<bool> b;
    set<int> st;
    void build(){
        sz.resize(n + 1);
        h.resize(n + 1);
        p.resize(n + 1);
        d.resize(n + 1);
        fill(1, 0);
        cnt = 0;
        hd.resize(n + 1);
        pos.resize(n + 1);
        fill_hld(1, 1);
        inv.resize(n + 1);
        for (int i = 1; i <= n; i++){
            inv[pos[i]] = i;
        }
        f.resize(n + 1);
        for (int i = 2; i <= n; i++) st.ins(i);
        
        b.resize(n + 1);
        for (auto [x, y]: ed){
            // x -> y
            if (d[x] > d[y]){
                b[x] = 1;
            }
            else {
                b[y] = 0;
            }
        }
    }
    int lca(int x, int y){
        while (hd[x] != hd[y]){
            if (d[hd[x]] > d[hd[y]]){
                swap(x, y);
            }
            y = p[hd[y]];
        }
        return ((d[x] > d[y]) ? y : x);
    }
    void upd(int l, int r, bool i){
        if (l > r) return;
        // cout<<"Yo "<<l<<" "<<b[l]<<" "<<i<<"\n";
        auto it = st.lower_bound(l);
        vector<int> er;
        while (it != st.end() && *it <= r){
            er.pb(*it++);
        }
        for (int j: er) st.erase(j);
        for (int j: er){
            // cout<<"Cool "<<inv[j]<<" "<<1 + (b[j] ^ i)<<"\n";
            f[inv[j]] = 1 + (b[j] ^ i);
        }
    }
    void set_r(int x, int l, bool i){
        // cout<<"Hi "<<x<<" "<<l<<" "<<i<<"\n";
        while (true){
            if (d[l] < d[hd[x]]){
                // hd[x] -> x
                // x -> ... -> hd[x]
                upd(pos[hd[x]], pos[x], i);
                x = p[hd[x]];
            }
            else {
                // l -> x
                upd(pos[l] + 1, pos[x], i);
                break;
            }
        }
    }
    void setp(int x, int y){
        int l = lca(x, y);
        set_r(x, l, 0);
        set_r(y, l, 1);
    }
    char get(int x, int y){
        if (d[x] > d[y]) swap(x, y);
        if (!f[y]) return 'B';
        return ((f[y] == 1) ? 'L' : 'R');
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<pii> g[n + 1], ed;
    for (int i = 1; i <= m; i++){
        int u, v; cin>>u>>v;
        ed.pb({u, v});
        if (u == v) continue;
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    
    vector<bool> used(n + 1);
    vector<int> t[n + 1], ind(n + 1);
    function<void(int)> dfs = [&](int v){
        used[v] = 1;
        for (auto p: g[v]){
            int i = p.ff;
            if (used[i]) continue;
            t[i].pb(v);
            t[v].pb(i);
            ind[i] = p.ss;
            dfs(i);
        }
    };
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            dfs(i);
        }
    }
    
    vector<int> d(n + 1, -1), par(n + 1);
    function<void(int, int)> fill_d = [&](int v, int pr){
        par[v] = pr;
        for (int i: t[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill_d(i, v);
        }
    };
    for (int i = 1; i <= n; i++){
        if (d[i] == -1){
            fill_d(i, 0);
        }
    }
    
    vector<int> dp(n + 1, -1);
    vector<pii> br;
    vector<bool> ban(m + 1);
    function<void(int, int)> solve = [&](int v, int pr){
        dp[v] = 0;
        for (auto p: g[v]){
            int i = p.ff;
            if (i == pr || v == par[i]) continue;
            dp[v] += (2 * (d[i] < d[v]) - 1);
        }
        for (int i: t[v]){
            if (i == pr) continue;
            solve(i, v);
            dp[v] += dp[i];
        }
        if (!dp[v]){
            ban[ind[v]] = 1;
            if (v != 1) br.pb({v, pr});
        }
    };
    for (int i = 1; i <= n; i++){
        if (dp[i] == -1){
            solve(i, 0);
        }
    }
    
    fill(used.begin(), used.end(), 0);
    
    vector<int> all[n + 1], gr(n + 1);
    int cnt = 0;
    function<void(int)> dfs1 = [&](int v){
        all[cnt].pb(v);
        gr[v] = cnt;
        used[v] = 1;
        for (auto [i, ii]: g[v]){
            if (used[i] || ban[ii]) continue;
            dfs1(i);
        }
    };
    
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            cnt++;
            dfs1(i);
        }
    }
    
    /*
    cout<<"hey"<<"\n";
    for (int i = 1; i <= cnt; i++){
        for (int j: all[i]){
            cout<<j<<" ";
        }
        cout<<"\n";
    }
    cout<<"hey"<<"\n";
     */
    
    TR T(cnt);
    for (auto [x, y]: br){
        x = gr[x]; y = gr[y];
        T.add(x, y);
    }
    T.build();
    
    int q; cin>>q;
    for (int i = 1; i <= q; i++){
        int x, y; cin>>x>>y;
        x = gr[x];
        y = gr[y];
        if (x != y) T.setp(x, y);
    }

    for (auto [x, y]: ed){
        x = gr[x]; y = gr[y];
        if (x == y){
            cout<<'B';
            continue;
        }
        // cout<<'T';
        cout<<T.get(x, y);
    }
}

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