Submission #571209

#	Time	Username	Problem	Language	Result	Execution time	Memory
571209		piOOE	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	168 ms	22512 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40