oj.uz

Submission #106805

# Submission time Handle Problem Language Result Execution time Memory
106805 2019-04-20T14:55:39 Z Frankenween One-Way Streets (CEOI17_oneway) C++17
100 / 100
 513 ms 46176 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 114 ms 10616 KB Output is correct
12 Correct 105 ms 12276 KB Output is correct
13 Correct 133 ms 14088 KB Output is correct
14 Correct 154 ms 18424 KB Output is correct
15 Correct 190 ms 22092 KB Output is correct
16 Correct 277 ms 38328 KB Output is correct
17 Correct 285 ms 40568 KB Output is correct
18 Correct 279 ms 38264 KB Output is correct
19 Correct 334 ms 42104 KB Output is correct
20 Correct 122 ms 12060 KB Output is correct
21 Correct 96 ms 11788 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 114 ms 10616 KB Output is correct
12 Correct 105 ms 12276 KB Output is correct
13 Correct 133 ms 14088 KB Output is correct
14 Correct 154 ms 18424 KB Output is correct
15 Correct 190 ms 22092 KB Output is correct
16 Correct 277 ms 38328 KB Output is correct
17 Correct 285 ms 40568 KB Output is correct
18 Correct 279 ms 38264 KB Output is correct
19 Correct 334 ms 42104 KB Output is correct
20 Correct 122 ms 12060 KB Output is correct
21 Correct 96 ms 11788 KB Output is correct
22 Correct 513 ms 41668 KB Output is correct
23 Correct 419 ms 39472 KB Output is correct
24 Correct 405 ms 39416 KB Output is correct
25 Correct 426 ms 46176 KB Output is correct
26 Correct 426 ms 41052 KB Output is correct
27 Correct 487 ms 39780 KB Output is correct
28 Correct 49 ms 6904 KB Output is correct
29 Correct 130 ms 12664 KB Output is correct
30 Correct 113 ms 12816 KB Output is correct
31 Correct 156 ms 13320 KB Output is correct
32 Correct 185 ms 21856 KB Output is correct