Submission #1226116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226116		takoshanava	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	89 ms	19268 KiB

oneway

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

const int N = 100123;
const int LOG = 18;
const long long 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];

struct Edge {
    int to, id, nxt;
};

Edge edges[2 * N];
int head[N], cnt = 0;

int edg_u[N], edg_v[N];
int ans[N];
void add_edge(int u, int v, int id) {
    edges[++cnt] = {v, id, head[u]};
    head[u] = cnt;
    edges[++cnt] = {u, id, head[v]};
    head[v] = cnt;
}

void dfs1(int v, int p, int id) {
    mark[v] = true;
    if (p == -1) h[v] = 0;
    zir[v] = h[v];
    for (int i = head[v]; i; i = edges[i].nxt) {
        int u = edges[i].to;
        int idx = edges[i].id;
        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] = true;
        } else if (u != p) {
            zir[v] = min(zir[v], h[u]);
        }
    }
}

void dfs2(int v) {
    mark[v] = true;
    col[v] = q;
    for (int i = head[v]; i; i = edges[i].nxt) {
        int u = edges[i].to;
        if (!mark[u]) dfs2(u);
    }
}

void dfs3(int v, int p) {
    mark[v] = true;
    par[0][v] = p;
    for (int i = 1; i < LOG; i++) par[i][v] = par[i - 1][par[i - 1][v]];
    for (int i = head[v]; i; i = edges[i].nxt) {
        int u = edges[i].to;
        if (u != p && !mark[u]) {
            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] = true;
    for (int i = head[v]; i; i = edges[i].nxt) {
        int u = edges[i].to;
        int idx = edges[i].id;
        if (u != p && !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_u[id]];
        int b = col[edg_v[id]];
        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;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    cnt = 0;
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        edg_u[i] = a;
        edg_v[i] = b;
        add_edge(a, b, 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);

    memset(head, 0, sizeof(head));
    cnt = 0;
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= m; i++) {
        if (!brr[i]) {
            add_edge(edg_u[i], edg_v[i], i);
        }
    }

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

    memset(head, 0, sizeof(head));
    cnt = 0;
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= n; i++) {
        h[i] = 0;
        man[i] = INF;
        mos[i] = INF;
    }
    for (int i = 1; i <= m; i++) {
        if (brr[i]) {
            add_edge(col[edg_u[i]], col[edg_v[i]], 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: In function 'int main()':
oneway.cpp:152:18: warning: overflow in conversion from 'long long int' to 'int' changes value from '3000000000000000000' to '-164888576' [-Woverflow]
  152 |         man[i] = INF;
      |                  ^~~
oneway.cpp:153:18: warning: overflow in conversion from 'long long int' to 'int' changes value from '3000000000000000000' to '-164888576' [-Woverflow]
  153 |         mos[i] = INF;
      |                  ^~~

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