oj.uz

Submission #881875

# Submission time Handle Problem Language Result Execution time Memory
881875 2023-12-02T06:56:12 Z Sharky One-Way Streets (CEOI17_oneway) C++17
30 / 100
 78 ms 22212 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];
pair<int, int> up[N], down[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) {
    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];
}

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++) {
        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'});
    }
    lift[1][0] = 1;
    pre(1);
    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 (u != lca) ans[up[u].first] = up[u].second, u = pa[u];
        while (v != lca) ans[up[v].first] = (up[v].second == 'R' ? 'L' : 'R'), v = pa[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 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 4 ms 10584 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 3 ms 10332 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 4 ms 10584 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 3 ms 10332 KB Output is correct
11 Correct 26 ms 15436 KB Output is correct
12 Correct 38 ms 16208 KB Output is correct
13 Correct 51 ms 17232 KB Output is correct
14 Correct 66 ms 21288 KB Output is correct
15 Incorrect 78 ms 22212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 4 ms 10584 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 3 ms 10332 KB Output is correct
11 Correct 26 ms 15436 KB Output is correct
12 Correct 38 ms 16208 KB Output is correct
13 Correct 51 ms 17232 KB Output is correct
14 Correct 66 ms 21288 KB Output is correct
15 Incorrect 78 ms 22212 KB Output isn't correct
16 Halted 0 ms 0 KB -