Submission #533903

#	Time	Username	Problem	Language	Result	Execution time	Memory
533903		alextodoran	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	299 ms	41188 KiB

oneway

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int BITS = 18;

int n, m;
int eu[N_MAX + 2], ev[N_MAX + 2];
vector <int> adj[N_MAX + 2];

multiset <pair <int, int>> es;

bool seen[N_MAX + 2];
int parent[N_MAX + 2];
int level[N_MAX + 2];
int minAbove[N_MAX + 2];

bool bridge[N_MAX + 2];

void dfs (int u) {
    seen[u] = true;
    minAbove[u] = level[u];
    for (int v : adj[u]) {
        if (seen[v] == false) {
            parent[v] = u;
            level[v] = level[u] + 1;
            dfs(v);
            minAbove[u] = min(minAbove[u], minAbove[v]);
        } else if (v != parent[u] || es.count(make_pair(u, v)) > 1) {
            minAbove[u] = min(minAbove[u], level[v]);
        }
    }
    if (minAbove[u] >= level[u]) {
        bridge[u] = true;
    }
}

int DSU[N_MAX + 2];
void DSUinit () {
    for (int u = 1; u <= n; u++) {
        DSU[u] = u;
    }
}
int DSUroot (int u) {
    return (DSU[u] == u ? u : DSU[u] = DSUroot(DSU[u]));
}
void DSUjoin (int u, int v) {
    DSU[DSUroot(u)] = DSUroot(v);
}

vector <int> tree[N_MAX + 2];
int treeParent[N_MAX + 2];
int depth[N_MAX + 2];

void treeDfs (int u) {
    seen[u] = true;
    for (int v : tree[u]) {
        if (v != treeParent[u]) {
            treeParent[v] = u;
            depth[v] = depth[u] + 1;
            treeDfs(v);
        }
    }
}

int anc[N_MAX + 2][BITS];

int ancestor (int u, int len) {
    for (int b = BITS - 1; b >= 0; b--) {
        if ((1 << b) <= len) {
            u = anc[u][b];
            len -= (1 << b);
        }
    }
    return u;
}
int lca (int u, int v) {
    if (depth[u] > depth[v]) {
        u = ancestor(u, depth[u] - depth[v]);
    } else if (depth[v] > depth[u]) {
        v = ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int b = BITS - 1; b >= 0; b--) {
        if (anc[u][b] != anc[v][b]) {
            u = anc[u][b];
            v = anc[v][b];
        }
    }
    return treeParent[u];
}

int k;

int up[N_MAX + 2];
int down[N_MAX + 2];
int type[N_MAX + 2];

void propagate (int u) {
    seen[u] = true;
    for (int v : tree[u]) {
        if (v != treeParent[u]) {
            propagate(v);
            up[u] += up[v];
            down[u] += down[v];
        }
    }
    if (up[u] > 0) {
        type[u] = 1;
    } else if (down[u] > 0) {
        type[u] = 2;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        if (eu[i] != ev[i]) {
            adj[eu[i]].push_back(ev[i]);
            adj[ev[i]].push_back(eu[i]);
            es.insert(make_pair(eu[i], ev[i]));
            es.insert(make_pair(ev[i], eu[i]));
        }
    }

    for (int u = 1; u <= n; u++) {
        if (seen[u] == false) {
            dfs(u);
        }
    }

    DSUinit();
    for (int u = 1; u <= n; u++) {
        if (parent[u] != 0 && bridge[u] == false) {
            DSUjoin(u, parent[u]);
        }
    }
    for (int u = 1; u <= n; u++) {
        if (parent[u] != 0 && bridge[u] == true) {
            int x = DSUroot(u), y = DSUroot(parent[u]);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
    }

    fill(seen + 1, seen + n + 1, false);
    for (int u = 1; u <= n; u++) {
        if (DSU[u] == u && seen[u] == false) {
            treeDfs(u);
        }
    }
    for (int u = 1; u <= n; u++) {
        anc[u][0] = treeParent[u];
    }
    for (int b = 1; b < BITS; b++) {
        for (int u = 1; u <= n; u++) {
            anc[u][b] = anc[anc[u][b - 1]][b - 1];
        }
    }

    cin >> k;
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        int x = DSUroot(u), y = DSUroot(v);
        int z = lca(x, y);
        up[x]++; up[z]--;
        down[y]++; down[z]--;
    }
    fill(seen + 1, seen + n + 1, false);
    for (int u = 1; u <= n; u++) {
        if (DSU[u] == u && seen[u] == false) {
            propagate(u);
        }
    }

    for (int i = 1; i <= m; i++) {
        int x = DSUroot(eu[i]), y = DSUroot(ev[i]);
        if (x == y) {
            cout << 'B';
        } else if (y == treeParent[x]) {
            if (type[x] == 0) {
                cout << 'B';
            } else {
                cout << (type[x] == 1 ? 'R' : 'L');
            }
        } else {
            if (type[y] == 0) {
                cout << 'B';
            } else {
                cout << (type[y] == 1 ? 'L' : 'R');
            }
        }
    }
    cout << "\n";

    return 0;
}

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