Submission #881883

#	Time	Username	Problem	Language	Result	Execution time	Memory
881883		Sharky	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	163 ms	36180 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40