oj.uz

Submission #571209

# Submission time Handle Problem Language Result Execution time Memory
571209 2022-06-01T14:22:27 Z piOOE One-Way Streets (CEOI17_oneway) C++17
100 / 100
 168 ms 22512 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 100001, infI = 1e9 + 7;
const ll infL = 3e18;

int n, m, k;
int A[N], B[N], X[N], Y[N], tin[N], fup[N], T = 0, color[N], parent[N], jump[N], depth[N], idx_par[N];
bool bridge[N], used[N];

vector<pair<int, int>> g[N], new_g[N];
int p[N];

int get(int a) {
    return a == p[a] ? a : p[a] = get(p[a]);
}

bool mrg(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) {
        return false;
    }
    p[b] = a;
    return true;
}

void dfs(int v, int j) {
    tin[v] = fup[v] = T++;
    used[v] = true;
    for (auto [to, i]: g[v]) {
        if (i != j) {
            if (used[to]) {
                ckmn(fup[v], tin[to]);
            } else {
                dfs(to, i);
                ckmn(fup[v], fup[to]);
                if (fup[to] > tin[v]) {
                    bridge[i] = true;
                }
            }
        }
    }
}

string ans;

void paint(int v) {
    used[v] = true;
    color[v] = T;
    for (auto [to, i]: g[v]) {
        if (!bridge[i] && !used[to]) {
            paint(to);
        }
    }
}

void zhfs(int v) {
    assert(!used[v]);
    used[v] = true;
    if (depth[jump[jump[parent[v]]]] - depth[jump[parent[v]]] == depth[jump[parent[v]]] - depth[parent[v]]) {
        jump[v] = jump[jump[parent[v]]];
    } else {
        jump[v] = parent[v];
    }
//    assert(v != jump[v]);
    for (auto [to, i]: new_g[v]) {
        if (to != parent[v]) {
            depth[to] = depth[v] + 1;
            parent[to] = v;
            idx_par[to] = i;
            zhfs(to);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    while (depth[a] > depth[b]) {
        if (depth[jump[a]] >= depth[b]) {
            a = jump[a];
        } else {
            a = parent[a];
        }
    }
    while (a != b) {
        if (jump[a] != jump[b]) {
            a = jump[a];
            b = jump[b];
        } else {
            a = parent[a];
            b = parent[b];
        }
    }
    return a;
}

void union_path(int a, int c, int tp) {
    a = get(a);
    while (a != get(c)) {
        assert(mrg(parent[a], a));
        assert(idx_par[a] != -1);
        if (color[A[idx_par[a]]] == a) {
            if (tp == 0) {
                ans[idx_par[a]] = 'R';
            } else {
                ans[idx_par[a]] = 'L';
            }
        } else {
            if (tp == 1) {
                ans[idx_par[a]] = 'R';
            } else {
                ans[idx_par[a]] = 'L';
            }
        }
        a = get(a);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> A[i] >> B[i];
        --A[i], --B[i];
        g[A[i]].emplace_back(B[i], i);
        g[B[i]].emplace_back(A[i], i);
    }
    cin >> k;
    for (int i = 0; i < k; ++i) {
        cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }
    memset(used, 0, sizeof(used));
    memset(idx_par, -1, sizeof(idx_par));
    T = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            paint(i);
            ++T;
        }
    }
    for (int i = 0; i < m; ++i) {
        if (bridge[i]) {
            new_g[color[A[i]]].emplace_back(color[B[i]], i);
            new_g[color[B[i]]].emplace_back(color[A[i]], i);
        }
    }
    memset(used, 0, sizeof(used));
    for (int i = 0; i < T; ++i) {
        if (!used[i]) {
            parent[i] = jump[i] = i;
            zhfs(i);
        }
    }
    iota(p, p + T, 0);
    ans = string(m, 'B');
    for (int i = 0; i < k; ++i) {
        int a = color[X[i]];
        int b = color[Y[i]];
        int c = lca(a, b);
        union_path(a, c, 0);
        union_path(b, c, 1);
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 4 ms 5460 KB Output is correct
3 Correct 4 ms 5588 KB Output is correct
4 Correct 4 ms 5672 KB Output is correct
5 Correct 4 ms 5588 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 4 ms 5664 KB Output is correct
9 Correct 4 ms 5588 KB Output is correct
10 Correct 4 ms 5588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 4 ms 5460 KB Output is correct
3 Correct 4 ms 5588 KB Output is correct
4 Correct 4 ms 5672 KB Output is correct
5 Correct 4 ms 5588 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 4 ms 5664 KB Output is correct
9 Correct 4 ms 5588 KB Output is correct
10 Correct 4 ms 5588 KB Output is correct
11 Correct 57 ms 11304 KB Output is correct
12 Correct 52 ms 12332 KB Output is correct
13 Correct 60 ms 13412 KB Output is correct
14 Correct 81 ms 14884 KB Output is correct
15 Correct 75 ms 15504 KB Output is correct
16 Correct 89 ms 17996 KB Output is correct
17 Correct 77 ms 18824 KB Output is correct
18 Correct 96 ms 17948 KB Output is correct
19 Correct 75 ms 19788 KB Output is correct
20 Correct 48 ms 11928 KB Output is correct
21 Correct 43 ms 11840 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 4 ms 5460 KB Output is correct
3 Correct 4 ms 5588 KB Output is correct
4 Correct 4 ms 5672 KB Output is correct
5 Correct 4 ms 5588 KB Output is correct
6 Correct 3 ms 5588 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 4 ms 5664 KB Output is correct
9 Correct 4 ms 5588 KB Output is correct
10 Correct 4 ms 5588 KB Output is correct
11 Correct 57 ms 11304 KB Output is correct
12 Correct 52 ms 12332 KB Output is correct
13 Correct 60 ms 13412 KB Output is correct
14 Correct 81 ms 14884 KB Output is correct
15 Correct 75 ms 15504 KB Output is correct
16 Correct 89 ms 17996 KB Output is correct
17 Correct 77 ms 18824 KB Output is correct
18 Correct 96 ms 17948 KB Output is correct
19 Correct 75 ms 19788 KB Output is correct
20 Correct 48 ms 11928 KB Output is correct
21 Correct 43 ms 11840 KB Output is correct
22 Correct 168 ms 20172 KB Output is correct
23 Correct 152 ms 18988 KB Output is correct
24 Correct 136 ms 19248 KB Output is correct
25 Correct 143 ms 22512 KB Output is correct
26 Correct 136 ms 19856 KB Output is correct
27 Correct 151 ms 19076 KB Output is correct
28 Correct 29 ms 10572 KB Output is correct
29 Correct 71 ms 13004 KB Output is correct
30 Correct 67 ms 13164 KB Output is correct
31 Correct 67 ms 13260 KB Output is correct
32 Correct 112 ms 16320 KB Output is correct