제출 #1308864

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

oneway

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

#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using ll = long long;
const ll MAXN = 100005;
const ll MAXM = 100005;

vector<tuple<ll, ll, char>> edges[MAXN];
bool vis[MAXN];
ll tin[MAXN], low[MAXN];
bool is_bridge[MAXM];
ll timer = 0;

ll who[MAXN];
ll comp_num = 1;
stack<ll> st;

void find_bridges(ll v, ll peid) {
    if (vis[v]) return;
    vis[v] = 1;

    tin[v] = low[v] = timer++;
    st.push(v);

    for (auto[u, id, dir] : edges[v]) {
        if (id == peid) continue;
        if (!vis[u]) {
            find_bridges(u, id);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v]) {
                is_bridge[id] = 1;
                while (1) {
                    ll x = st.top();
                    st.pop();
                    who[x] = comp_num;
                    if (x == u) break;
                }
                comp_num++;
            }
        } else {
            low[v] = min(low[v], tin[u]);
        }
    }
}

vector<tuple<ll, ll, char>> tecc_edges[MAXN];
tuple<ll, ll, char> parent[MAXN];
ll depth[MAXN];
string ans;

struct DSU {
    vector<ll> p;

    DSU(ll n) {
        p.resize(n);
        iota(all(p), 0);
    }

    ll get(ll v) {
        if (p[v] == v) return v;
        return p[v] = get(p[v]);
    }

    void unite(ll par, ll v) {
        par = get(par);
        v = get(v);

        if (par == v) return;

        p[v] = par;
    }
};

void dfs(ll v, ll lca, bool up, DSU& dsu) {
    if (depth[v] <= depth[lca]) return;
    
    auto[u, id, dir] = parent[v];
    if (dsu.get(v) == v) {
        dsu.unite(u, v);
        dfs(u, lca, up, dsu);
    } else {
        dfs(dsu.get(v), lca, up, dsu);
    }

    if (up) ans[id] = dir == 'L' ? 'R' : 'L';
    else ans[id] = dir;
}

struct LCA {
    struct RMQ {
        vector<pair<ll, ll>> nodes;
        ll size = 1;

        RMQ(ll n) {
            while (size < n) size*=2;
            nodes.assign(2*size, {1e18, 1e18});
        }

        void build(vector<pair<ll, ll>>& a, ll x, ll lx, ll rx) {
            if (rx-lx == 1) {
                if (lx < a.size()) {
                    nodes[x] = a[lx];
                }
                return;
            }

            ll m = (lx+rx)/2;
            build(a, 2*x+1, lx, m);
            build(a, 2*x+2, m, rx);

            nodes[x] = min(nodes[2*x+1], nodes[2*x+2]);
        }

        void build(vector<pair<ll, ll>>& a) {
            build(a, 0, 0, size);
        }

        pair<ll, ll> query(ll l, ll r, ll x, ll lx, ll rx) {
            if (lx >= l && rx <= r) return nodes[x];
            if (rx <= l || lx >= r) return {1e18, 1e18};

            ll m = (lx+rx)/2;
            return min(query(l, r, 2*x+1, lx, m), query(l, r, 2*x+2, m , rx));
        }

        pair<ll, ll> query(ll l, ll r) {
            return query(l, r, 0, 0, size);
        }
    };

    vector<pair<ll, ll>> euler;
    vector<ll> first;
    RMQ rmq;

    LCA(ll root, ll n) : rmq(2*n) {
        first.assign(n, -1);
        dfs(root, -1, 0);
        rmq.build(euler);
    }

    void dfs(ll v, ll p, ll d) {
        euler.push_back({d, v});
        if (first[v] == -1) first[v] = euler.size()-1;

        depth[v] = d;

        for (auto[u, id, dir] : tecc_edges[v]) {
            if (u == p) continue;
            dfs(u, v, d+1);
            euler.push_back({d, v});

            parent[u] = {v, id, dir};
        }
    }

    ll get(ll v, ll u) {
        if (first[v] > first[u]) swap(v, u);
        return rmq.query(first[v], first[u]+1).se;
    }
};

void solve() {
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        ll v, u;
        cin >> v >> u;
        v--, u--;
        edges[v].push_back({u, i, 'R'});
        edges[u].push_back({v, i, 'L'});
    }

    for (ll v = 0; v < n; v++) tin[v] = low[v] = 1e18;

    for (ll v = 0; v < n; v++) {
        if (vis[v]) continue;
        find_bridges(v, -1);
    }

    for (ll v = 0; v < n; v++) {
        for (auto[u, id, dir] : edges[v]) {
            if (who[v] == who[u]) continue;
            tecc_edges[who[v]].push_back({who[u], id, dir});
        }
    }

    LCA lca(0, comp_num);

    ans.assign(m, 'B');
    DSU dsu(comp_num);

    ll q; cin >> q;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        a = who[a], b = who[b];

        ll c = lca.get(a, b);
        dfs(a, c, 1, dsu);
        dfs(b, c, 0, dsu);
    }

    cout << ans << '\n';
}

int main() {
    // freopen("promote.in", "r", stdin);
    // freopen("promote.out", "w", stdout);
 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

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