oj.uz

Submission #533903

# Submission time Handle Problem Language Result Execution time Memory
533903 2022-03-07T15:07:15 Z alextodoran One-Way Streets (CEOI17_oneway) C++17
100 / 100
 299 ms 41188 KB 
/**
 ____ ____ ____ ____ ____
||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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 4 ms 5240 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5292 KB Output is correct
7 Correct 4 ms 5292 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 4 ms 5240 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5292 KB Output is correct
7 Correct 4 ms 5292 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 151 ms 21208 KB Output is correct
12 Correct 161 ms 23740 KB Output is correct
13 Correct 176 ms 27100 KB Output is correct
14 Correct 230 ms 31436 KB Output is correct
15 Correct 217 ms 32788 KB Output is correct
16 Correct 266 ms 33428 KB Output is correct
17 Correct 230 ms 35836 KB Output is correct
18 Correct 249 ms 33620 KB Output is correct
19 Correct 205 ms 37424 KB Output is correct
20 Correct 174 ms 24640 KB Output is correct
21 Correct 141 ms 25020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 4 ms 5240 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5292 KB Output is correct
7 Correct 4 ms 5292 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 151 ms 21208 KB Output is correct
12 Correct 161 ms 23740 KB Output is correct
13 Correct 176 ms 27100 KB Output is correct
14 Correct 230 ms 31436 KB Output is correct
15 Correct 217 ms 32788 KB Output is correct
16 Correct 266 ms 33428 KB Output is correct
17 Correct 230 ms 35836 KB Output is correct
18 Correct 249 ms 33620 KB Output is correct
19 Correct 205 ms 37424 KB Output is correct
20 Correct 174 ms 24640 KB Output is correct
21 Correct 141 ms 25020 KB Output is correct
22 Correct 299 ms 36928 KB Output is correct
23 Correct 269 ms 34664 KB Output is correct
24 Correct 287 ms 34832 KB Output is correct
25 Correct 277 ms 41188 KB Output is correct
26 Correct 257 ms 36392 KB Output is correct
27 Correct 261 ms 34792 KB Output is correct
28 Correct 148 ms 17404 KB Output is correct
29 Correct 173 ms 25172 KB Output is correct
30 Correct 178 ms 26092 KB Output is correct
31 Correct 188 ms 25752 KB Output is correct
32 Correct 185 ms 31540 KB Output is correct