Submission #1005152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005152		SulA	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3027 ms	12632 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> par, size;

    DSU(int n = 0) {
        par.resize(n+1, 0);
        size.resize(n+1, 0);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
        }
    }

    int find(int v) {
        return par[v] == v ? v : par[v] = find(par[v]);
    }

    void merge(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (size[a] < size[b]) swap(a,b);
            par[b] = a;
            size[a] += size[b];
        }
    }
};

const int MAXN = 100000;
vector<int> adj[MAXN+1];
vector<int> comp[MAXN+1];
vector<pair<int,int>> bridges, graph;
map<pair<int,int>,int> ind;
map<pair<int,int>,pair<int,int>> compToOriginal;
DSU d;

int dep[MAXN + 1], low[MAXN + 1], par[17][MAXN + 1], lay[MAXN + 1];
void dfs1(int v, int p) {
    dep[v] = low[v] = dep[p] + 1;
    for (int u : adj[v]) {
        if (u == p) continue;
        if (dep[u] == 0) {
            dfs1(u, v);
            low[v] = min(low[v], low[u]);
        } else {
            low[v] = min(low[v], dep[u]);
            d.merge(v, u);
        }
    }
    if (v == 1) return;
    if (low[v] == dep[v]) {
        if (binary_search(graph.begin(), graph.end(), make_pair(p,v))) {
            bridges.push_back({p,v});
        } else {
            bridges.push_back({v,p});

        }
    } else {
        d.merge(p, v);
    }
}

void dfs2(int v, int p) {
    par[0][v] = p;
    lay[v] = lay[p] + 1;
    for (int k = 1; k < 17; k++) {
        par[k][v] = par[k-1][par[k-1][v]];
    }
    for (auto u : comp[v]) if (u != p) {
            dfs2(u, v);
        }
}

int lca(int a, int b) {
    if (lay[a] > lay[b]) swap(a, b);
    int dif = lay[b] - lay[a];
    for (int i = 17; i >= 0; i--) {
        if (dif & (1 << i)) {
            b = par[i][b];
        }
    }
    if (a == b) return a;

    for (int i = 17; i >= 0; i--) {
        if (par[i][a] != par[i][b]) {
            a = par[i][a];
            b = par[i][b];
        }
    }

    return par[0][a];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n,m; cin >> n >> m;
    char ans[m];
    fill(ans, ans + m, 'B');
    d = DSU(n);
    for (int i = 0; i < m; i++) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        graph.push_back({a,b});
        ind[{a,b}] = i;
    }
    sort(graph.begin(), graph.end());
    dfs1(1, 0);
    sort(bridges.begin(), bridges.end());
    for (auto [a,b] : bridges) {
        int compa = d.find(a), compb = d.find(b);
        comp[compa].push_back(compb);
        comp[compb].push_back(compa);
        compToOriginal[{min(compa, compb), max(compa, compb)}] = {a,b};
    }
    int root;
    for (int v = 1; v <= n; v++) if (v == d.find(v)) {
            root = v;
            dfs2(root, root);
            break;
        }
    int q; cin >> q;
    while (q--) {
        int a,b; cin >> a >> b;
        a = d.find(a), b = d.find(b);
        if (a == b) continue;
        int L = lca(a,b);

        while (a != L) {
            int p = par[0][a];
            auto [oldv, oldu] = compToOriginal[{min(a,p), max(a,p)}];
            if (ind.find({oldv, oldu}) != ind.end()) {
                int index = ind[{oldv, oldu}];
                ans[index] = 'R';
            } else {
                int index = ind[{oldu, oldv}];
                ans[index] = 'L';
            }
            a = p;
        }
        while (b != L) {
            int p = par[0][b];
            auto [oldu, oldv] = compToOriginal[{min(b,p), max(b,p)}];
            if (ind.find({oldv, oldu}) != ind.end()) {
                int index = ind[{oldv, oldu}];
                ans[index] = 'R';
            } else {
                int index = ind[{oldu, oldv}];
                ans[index] = 'L';
            }
            b = p;
        }
    }
    for (char c : ans) cout << c;
}

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