Submission #106805

#	Time	Username	Problem	Language	Result	Execution time	Memory
106805		Frankenween	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	513 ms	46176 KiB

oneway

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct edge {
    ll u, ind;
};


void solve() {
    ll n, m;
    cin >> n >> m;
    vector<vector<edge>> g(n);
    vector<pair<ll, ll>> directions(m);
    vector<bool> used(n);
    for (int i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].pb({b, i});
        g[b].pb({a, i});
        directions[i] = {a, b};
    }

    vector<ll> tin(n, -1), up(n, -1);
    vector<bool> bridge(m);
    ll timer = 0;

    function<void(ll, ll)> dfs1 = [&](ll v, ll pr) {
        tin[v] = timer;
        up[v] = timer;
        timer++;
        used[v] = true;
        for (auto e : g[v]) {
            if (e.ind == pr) {
                continue;
            }
            if (used[e.u]) {
                up[v] = min(up[v], tin[e.u]);
                continue;
            }
            dfs1(e.u, e.ind);
            up[v] = min(up[v], up[e.u]);
            if (up[e.u] > tin[v]) {
                bridge[e.ind] = true;
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs1(i, -1);
        }
    }

    timer = 0;
    tin.assign(n, 0);
    vector<ll> comp(n);
    used.assign(n, false);

    function<void(ll)> dfs2 = [&](ll v) {
        comp[v] = timer;
        used[v] = true;
        for (auto e : g[v]) {
            if (used[e.u] or bridge[e.ind]) {
                continue;
            }
            dfs2(e.u);
        }
    };

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs2(i);
            timer++;
        }
    }

    g.clear();
    n = timer;
    g.assign(n, {});
    for (int i = 0; i < m; i++) {
        if (!bridge[i]) {
            continue;
        }
        ll a = comp[directions[i].first], b = comp[directions[i].second];
        g[a].pb({b, i});
        g[b].pb({a, i});
    }
    ll L = 20;
    vector<vector<ll>> dp(n, vector<ll>(L, -1));
    timer = 0;
    tin.clear();
    tin.assign(n, -1);
    used.assign(n, false);
    vector<ll> tout(n), pred(n, -1), pr_edge(n), limit(n);

    function<void(ll, ll)> dfs3 = [&](ll v, ll pr) {
        tin[v] = timer;
        timer++;
        dp[v][0] = pr;
        used[v] = true;
        for (int i = 1; i < L; i++) {
            dp[v][i] = dp[dp[v][i - 1]][i - 1];
        }
        for (auto e : g[v]) {
            if (e.u != pr) {
                pred[e.u] = v;
                pr_edge[e.u] = e.ind;
                dfs3(e.u, v);
            }
        }
        tout[v] = timer;
        timer++;
    };

    for (int i = 0; i < n; i++) {
        limit[i] = i;
        if (!used[i]) {
            dfs3(i, i);
        }
    }

    function<bool(ll, ll)> parent = [&](ll v, ll u) {
        return (tin[v] <= tin[u] and tout[v] >= tout[u]);
    };

    function<ll(ll, ll)> lca = [&](ll v, ll u) {
        if (parent(v, u)) {
            return v;
        }
        if (parent(u, v)) {
            return u;
        }
        ll cnt = v;
        for (int i = L - 1; i >= 0; i--) {
            if (!parent(dp[cnt][i], u)) {
                cnt = dp[cnt][i];
            }
        }
        return dp[cnt][0];
    };

    ll q;
    cin >> q;
    vector<bool> need_up(n, false), visited(n, false);
    while (q--) {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        x = comp[x];
        y = comp[y];
        if (x == y) {
            continue;
        }
        ll par = lca(x, y);
        if (x != par) {
            need_up[x] = true;
        }
        if (parent(par, limit[x])) {
            limit[x] = par;
        }
        if (parent(par, limit[y])) {
            limit[y] = par;
        }
    }

    // dsu
    vector<ll> dsu_pr(n), dsu_sz(n), highest(n);
    for (int i = 0; i < n; i++) {
        dsu_pr[i] = i;
        highest[i] = i;
        dsu_sz[i] = 1;
    }

    function<ll(ll)> lead = [&](ll v) {
        if (dsu_pr[v] == v) {
            return v;
        }
        ll r = lead(dsu_pr[v]);
        dsu_pr[v] = r;
        return r;
    };

    function<void(ll, ll)> unite = [&](ll v, ll u) {
        v = lead(v);
        u = lead(u);
        if (u == v) {
            return;
        }
        ll new_h;
        if (parent(highest[v], highest[u])) {
            new_h = highest[v];
        } else {
            new_h = highest[u];
        }
        if (dsu_sz[v] < dsu_sz[u]) {
            swap(v, u);
        }
        dsu_pr[u] = v;
        dsu_sz[v] += dsu_sz[u];
        highest[v] = new_h;
    };
    // dsu
    string answer(m, 'B');
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            ll v = i;
            ll go_up = limit[v];
            while (parent(go_up, v) and go_up != v) {
                visited[v] = true;
                ll previous = pred[v];
                ll a = comp[directions[pr_edge[v]].first];
                if (a == v) {
                    if (need_up[i]) {
                        answer[pr_edge[v]] = 'R';
                    } else {
                        answer[pr_edge[v]] = 'L';
                    }
                } else {
                    if (need_up[i]) {
                        answer[pr_edge[v]] = 'L';
                    } else {
                        answer[pr_edge[v]] = 'R';
                    }
                }
                unite(v, previous);
                v = highest[lead(v)];
                if (parent(limit[v], go_up)) {
                    go_up = limit[v];
                }
            }
        }
    }
    cout << answer;
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

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