oj.uz

Submission #881883

# Submission time Handle Problem Language Result Execution time Memory
881883 2023-12-02T07:25:23 Z Sharky One-Way Streets (CEOI17_oneway) C++17
100 / 100
 163 ms 36180 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int lg = 18;

#define fi first
#define se second

vector<pair<int, int>> adj[N];
pair<int, int> edges[N];
set<int> b;
vector<char> ans(N, 'B');
int n, m, pairs, low[N], st[N], timer = 0, k = 0, bcc[N], road_id = 0, lift[N][lg], dep[N], pa[N], f[N];
pair<int, int> up[N], down[N];
bool vis[N];

struct edge {
    int v, id;
    char dir;
};

vector<edge> g[N];

void dfs(int u, int p) {
    low[u] = st[u] = ++timer;
    for (auto& [v, id] : adj[u]) {
        if (!st[v]) {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > st[u]) b.insert(id);
        } else if (id != p) {
            low[u] = min(low[u], st[v]);
        }
    }
}

void Dfs(int u) {
    bcc[u] = k;
    for (auto& [v, id] : adj[u]) {
        if (b.count(id)) continue;
        if (!bcc[v]) Dfs(v);
    }
}

void pre(int u) {
    vis[u] = 1;
    for (int i = 1; i < lg; i++) lift[u][i] = lift[lift[u][i - 1]][i - 1];
    for (auto& [v, id, dir] : g[u]) {
        if (lift[u][0] != v) {
            dep[v] = dep[u] + 1;
            pa[v] = u;
            lift[v][0] = u;
            pre(v);
        }
    }
}

int jump(int sta, int dist) {
    for (int i = lg - 1; i >= 0; i--) if (dist & (1 << i)) sta = lift[sta][i];
    return sta;
}

int get_lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    v = jump(v, dep[v] - dep[u]);
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--) {
        int ut = lift[u][i], vt = lift[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return lift[u][0];
}

int find(int u) {
    return f[u] == u ? u : f[u] = find(f[u]);
}

void merge(int u, int v) {
    f[find(u)] = find(v);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        road_id++;
        adj[u].push_back({v, road_id});
        adj[v].push_back({u, road_id});
        edges[road_id] = {u, v};
    }
    for (int i = 1; i <= n; i++) if (!st[i]) dfs(i, 0);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        if (!bcc[i]) {
            k++;
            Dfs(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        int u = bcc[edges[i].fi], v = bcc[edges[i].se];
        if (u == v) continue;
        g[u].push_back((edge) {v, i, 'R'});
        g[v].push_back((edge) {u, i, 'L'});
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        lift[i][0] = 1;
        pre(i);
    }
    for (int i = 1; i <= m; i++) {
        int u = bcc[edges[i].fi], v = bcc[edges[i].se];
        if (u == v) continue;
        if (dep[u] > dep[v]) up[u] = {i, 'R'};
        else up[v] = {i, 'L'};
    }
    cin >> pairs;
    while (pairs--) {
        int u, v;
        cin >> u >> v;
        u = bcc[u], v = bcc[v];
        int lca = get_lca(u, v);
        while (dep[u] > dep[lca]) {
            ans[up[u].first] = up[u].second; 
            merge(u, pa[u]);
            u = find(u);
        }
        while (dep[v] > dep[lca]) {
            ans[up[v].first] = (up[v].second == 'R' ? 'L' : 'R');
            merge(v, pa[v]);
            v = find(v);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i];
    cout << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11256 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10928 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11256 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10928 KB Output is correct
11 Correct 29 ms 16716 KB Output is correct
12 Correct 40 ms 17368 KB Output is correct
13 Correct 53 ms 20304 KB Output is correct
14 Correct 70 ms 22544 KB Output is correct
15 Correct 79 ms 23916 KB Output is correct
16 Correct 122 ms 29856 KB Output is correct
17 Correct 110 ms 31004 KB Output is correct
18 Correct 120 ms 29764 KB Output is correct
19 Correct 106 ms 32000 KB Output is correct
20 Correct 34 ms 19036 KB Output is correct
21 Correct 34 ms 18836 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11256 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 11096 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10928 KB Output is correct
11 Correct 29 ms 16716 KB Output is correct
12 Correct 40 ms 17368 KB Output is correct
13 Correct 53 ms 20304 KB Output is correct
14 Correct 70 ms 22544 KB Output is correct
15 Correct 79 ms 23916 KB Output is correct
16 Correct 122 ms 29856 KB Output is correct
17 Correct 110 ms 31004 KB Output is correct
18 Correct 120 ms 29764 KB Output is correct
19 Correct 106 ms 32000 KB Output is correct
20 Correct 34 ms 19036 KB Output is correct
21 Correct 34 ms 18836 KB Output is correct
22 Correct 146 ms 31784 KB Output is correct
23 Correct 146 ms 31836 KB Output is correct
24 Correct 163 ms 32144 KB Output is correct
25 Correct 159 ms 36180 KB Output is correct
26 Correct 137 ms 33068 KB Output is correct
27 Correct 152 ms 32136 KB Output is correct
28 Correct 24 ms 14160 KB Output is correct
29 Correct 49 ms 20824 KB Output is correct
30 Correct 55 ms 20976 KB Output is correct
31 Correct 48 ms 21352 KB Output is correct
32 Correct 87 ms 25024 KB Output is correct