Submission #571271

#	Time	Username	Problem	Language	Result	Execution time	Memory
571271		piOOE	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	183 ms	32116 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], idx_par[N], lca[N];
bool bridge[N], used[N];

vector<pair<int, int>> g[N], new_g[N], qu[N];
int p[N], sz[N], pp[N], ssz[N], leader[N];

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

int gget(int a) {
    return a == pp[a] ? a : pp[a] = gget(pp[a]);
}

int mrg(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) {
        return 0;
    }
    sz[a] += sz[b];
    p[b] = a;
    return true;
}

int mmrg(int a, int b) {
    a = gget(a);
    b = gget(b);
    assert(a != b);
    if (ssz[a] < ssz[b]) {
        swap(a, b);
    }
    ssz[a] += ssz[b];
    pp[b] = a;
    return a;
}

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) {
    used[v] = true;
    leader[v] = v;
    for (auto [to, i]: new_g[v]) {
        if (to != parent[v]) {
            parent[to] = v;
            idx_par[to] = i;
            zhfs(to);
            leader[mmrg(v, to)] = v;
        }
    }
    for (auto[to, i] : qu[v]) {
        if (used[to]) {
            lca[i] = leader[gget(to)];
        }
    }
}

void union_path(int a, int c, int tp) {
    a = get(a);
    while (a != get(c)) {
        mrg(parent[a], a);
        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];
    }
    iota(leader, leader + n, 0);
    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);
        }
    }
    for (int i = 0; i < k; ++i) {
        qu[color[X[i]]].emplace_back(color[Y[i]], i);
        qu[color[Y[i]]].emplace_back(color[X[i]], i);
    }
    memset(used, 0, sizeof(used));
    fill(sz, sz + T, 1);
    fill(ssz, ssz + T, 1);
    iota(pp, pp + T, 0);
    iota(p, p + T, 0);
    for (int i = 0; i < T; ++i) {
        if (!used[i]) {
            zhfs(i);
        }
    }
    ans = string(m, 'B');
    for (int i = 0; i < k; ++i) {
        int a = color[X[i]];
        int b = color[Y[i]];
        int c = lca[i];
        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