Submission #1226907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226907		lukasuliashvili	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	138 ms	32948 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for(int i = a; i <= b; i++)

const int N = 100123, LOG = 18;
const int64_t INF = 3e18;

int n, m, p, dep[N], low[N], col[N], anc[LOG][N], up[N], down[N];
bool bridge[N], vis[N];

int u[N], v[N], dir[N];

int hd[N], nxt[2 * N], to[2 * N], id[2 * N], ecnt = 0;
void add(int a, int b, int i) {
    to[++ecnt] = b; id[ecnt] = i; nxt[ecnt] = hd[a]; hd[a] = ecnt;
    to[++ecnt] = a; id[ecnt] = i; nxt[ecnt] = hd[b]; hd[b] = ecnt;
}

void dfs1(int x, int par, int pid) {
    vis[x] = 1;
    if (par == -1) dep[x] = 0;
    low[x] = dep[x];
    for (int i = hd[x]; i; i = nxt[i]) {
        int y = to[i], idx = id[i];
        if (idx == pid) continue;
        if (!vis[y]) {
            dep[y] = dep[x] + 1;
            dfs1(y, x, idx);
            low[x] = min(low[x], low[y]);
            if (low[y] > dep[x]) bridge[idx] = 1;
        } else if (y != par) {
            low[x] = min(low[x], dep[y]);
        }
    }
}

void dfs2(int x, int c) {
    col[x] = c; vis[x] = 1;
    for (int i = hd[x]; i; i = nxt[i]) {
        int y = to[i];
        if (!bridge[id[i]] && !vis[y]) dfs2(y, c);
    }
}

int h[N];
void dfs3(int x, int par) {
    vis[x] = 1; anc[0][x] = par;
    rep(i,1,LOG-1) anc[i][x] = anc[i-1][anc[i-1][x]];
    for (int i = hd[x]; i; i = nxt[i]) {
        int y = to[i];
        if (!vis[y] && y != par) {
            h[y] = h[x] + 1;
            dfs3(y, x);
        }
    }
    up[x] = down[x] = h[x];
}

int climb(int x, int d) {
    rep(i,0,LOG-1) if (d & (1 << i)) x = anc[i][x];
    return x;
}

int get_lca(int a, int b) {
    if (h[a] < h[b]) swap(a, b);
    a = climb(a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = LOG - 1; i >= 0; i--) {
        if (anc[i][a] != anc[i][b]) {
            a = anc[i][a];
            b = anc[i][b];
        }
    }
    return anc[0][a];
}

void dfs4(int x, int par, int pid = 0) {
    vis[x] = 1;
    for (int i = hd[x]; i; i = nxt[i]) {
        int y = to[i], idx = id[i];
        if (y != par && !vis[y]) {
            dfs4(y, x, idx);
            up[x] = min(up[x], up[y]);
            down[x] = min(down[x], down[y]);
        }
    }
    if (pid) {
        int a = col[u[pid]], b = col[v[pid]];
        if (up[x] != h[x]) dir[pid] = (a == par ? 1 : 2);
        else if (down[x] != h[x]) dir[pid] = (a == par ? 2 : 1);
        else dir[pid] = 0;
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    rep(i,1,m) {
        cin >> u[i] >> v[i];
        add(u[i], v[i], i);
        bridge[i] = dir[i] = 0;
    }

    fill(begin(vis), end(vis), 0);
    rep(i,1,n) if (!vis[i]) dfs1(i, -1, -1);

    fill(begin(hd), end(hd), 0); ecnt = 0;
    fill(begin(vis), end(vis), 0);
    rep(i,1,m) if (!bridge[i]) add(u[i], v[i], i);

    int comp = 0;
    rep(i,1,n) if (!vis[i]) dfs2(i, ++comp);

    fill(begin(hd), end(hd), 0); ecnt = 0;
    fill(begin(vis), end(vis), 0);
    rep(i,1,n) h[i] = up[i] = down[i] = INF;
    rep(i,1,m) if (bridge[i]) add(col[u[i]], col[v[i]], i);

    rep(i,1,comp) if (!vis[i]) h[i] = 0, dfs3(i, i);

    cin >> p;
    rep(i,1,p) {
        int a, b; cin >> a >> b;
        a = col[a]; b = col[b];
        if (a == b) continue;
        int c = get_lca(a, b);
        up[b] = min(up[b], h[c]);
        down[a] = min(down[a], h[c]);
    }

    fill(begin(vis), end(vis), 0);
    rep(i,1,comp) if (!vis[i]) dfs4(i, i);

    rep(i,1,m) {
        if (dir[i] == 1) cout << "R";
        else if (dir[i] == 2) cout << "L";
        else cout << "B";
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40