Submission #1226114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226114		takoshanava	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	247 ms	327680 KiB

oneway

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 1e5 + 123;
const int LOG = 18;
const int INF = 3e18;

int n, m, q;
int h[N], zir[N], col[N], par[LOG][N], man[N], mos[N];
bool brr[N], mark[N];
vector<pair<int,int>> g[N];
pair<pair<int,int>, int> edg[N];
int ans[N];

void dfs1(int v, int p, int id) {
    mark[v] = 1;
    if (p == -1) h[v] = 0;
    zir[v] = h[v];
    for (auto &[u, idx] : g[v]) {
        if (idx == id) continue;
        if (!mark[u]) {
            h[u] = h[v] + 1;
            dfs1(u, v, idx);
            zir[v] = min(zir[v], zir[u]);
            if (zir[u] > h[v]) brr[idx] = 1;
        } else if (u != p) {
            zir[v] = min(zir[v], h[u]);
        }
    }
}

void dfs2(int v) {
    mark[v] = 1;
    col[v] = q;
    for (auto &[u, _] : g[v]) {
        if (!mark[u]) dfs2(u);
    }
}

void dfs3(int v, int p) {
    mark[v] = 1;
    par[0][v] = p;
    for (int i = 1; i < LOG; i++) par[i][v] = par[i-1][par[i-1][v]];
    for (auto &[u, _] : g[v]) {
        if (u != p) {
            h[u] = h[v] + 1;
            dfs3(u, v);
        }
    }
    man[v] = h[v];
    mos[v] = h[v];
}

int jump(int v, int d) {
    for (int i = 0; i < LOG; i++)
        if (d & (1 << i))
            v = par[i][v];
    return v;
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    u = jump(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; i--) {
        if (par[i][u] != par[i][v]) {
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

void dfs4(int v, int p, int id = 0) {
    mark[v] = 1;
    for (auto &[u, idx] : g[v]) {
        if (u != p and !mark[u]) {
            dfs4(u, v, idx);
            man[v] = min(man[v], man[u]);
            mos[v] = min(mos[v], mos[u]);
        }
    }
    if (id) {
        int a = col[edg[id].fs.fs];
        int b = col[edg[id].fs.sc];
        if (man[v] != h[v]) ans[id] = (a == p ? 1 : 2);
        else if (mos[v] != h[v]) ans[id] = (a == p ? 2 : 1);
        else ans[id] = 0;
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        edg[i] = {{a, b}, i};
        g[a].pb({b, i});
        g[b].pb({a, i});
        brr[i] = false;
        ans[i] = 0;
    }

    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= n; i++) if (!mark[i]) dfs1(i, -1, -1);

    for (int i = 1; i <= n; i++) {
        g[i].clear();
        mark[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        if (!brr[i]) {
            int a = edg[i].fs.fs, b = edg[i].fs.sc;
            g[a].pb({b, i});
            g[b].pb({a, i});
        }
    }

    q = 0;
    for (int i = 1; i <= n; i++) {
        if (!mark[i]) {
            q++;
            dfs2(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        g[i].clear();
        mark[i] = 0;
        h[i] = 0;
        man[i] = INF;
        mos[i] = INF;
    }
    for (int i = 1; i <= m; i++) {
        if (brr[i]) {
            int a = col[edg[i].fs.fs], b = col[edg[i].fs.sc];
            g[a].pb({b, i});
            g[b].pb({a, i});
        }
    }

    for (int i = 1; i <= q; i++) if (!mark[i]) dfs3(i, i);

    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        int a, b; cin >> a >> b;
        a = col[a], b = col[b];
        if (a == b) continue;
        int c = lca(a, b);
        man[b] = min(man[b], h[c]);
        mos[a] = min(mos[a], h[c]);
    }

    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= q; i++) if (!mark[i]) dfs4(i, i);

    for (int i = 1; i <= m; i++) {
        if (ans[i] == 1) cout << "R";
        else if (ans[i] == 2) cout << "L";
        else cout << "B";
    }
}

Compilation message (stderr)

oneway.cpp:10:17: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   10 | const int INF = 3e18;
      |                 ^~~~

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