Submission #106788

#	Time	Username	Problem	Language	Result	Execution time	Memory
106788		Frankenween	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	942 ms	263168 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 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;
};


vector<vector<edge>> g;
vector<pair<ll, ll>> directions;
vector<ll> tin, up;
vector<bool> bridge;
vector<ll> comp;
ll L = 20;
vector<vector<ll>> dp;
vector<ll> tout, pred, pr_edge, limit;
ll timer = 0;


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


void dfs2(ll v) {
    tin[v] = 1;
    comp[v] = timer;
    for (auto e : g[v]) {
        if (tin[e.u] == 1 or bridge[e.ind]) {
            continue;
        }
        dfs2(e.u);
    }
}


void dfs3(ll v, ll pr) {
    tin[v] = timer;
    timer++;
    dp[v][0] = pr;
    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++;
}


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

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];
}


void solve() {
    ll n, m;
    cin >> n >> m;
    g.resize(n);
    directions.resize(m);
    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};
    }

    tin.resize(n, -1);
    up.resize(n, -1);
    bridge.resize(m);

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

    timer = 0;
    tin.assign(n, 0);
    comp.resize(n);

    for (int i = 0; i < n; i++) {
        if (tin[i] == 0) {
            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});
    }

    dp.resize(n, vector<ll>(L, -1));
    timer = 0;
    tin.clear();
    tin.assign(n, -1);
    tout.resize(n);
    pred.resize(n, -1);
    pr_edge.resize(n);
    limit.resize(n);

    for (int i = 0; i < n; i++) {
        limit[i] = i;
        if (tin[i] == -1) {
            dfs3(i, i);
        }
    }

    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;
        }
        need_up[x] = true;
        ll par = lca(x, y);
        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)];
                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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40