Submission #1257169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257169		nikaa123	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	164 ms	37580 KiB

oneway

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

const int maxn = 100005;

int n, m;
bool isbridge[maxn], ismulti[maxn];
int tin[maxn], low[maxn], comp[maxn];
int timer = 0;
int binlift[maxn][20];
vector<pair<int,int>> adj[maxn];    // (neighbor, edge_id)
vector<int> bcadj[maxn];            // bridge tree adjacency (components)
int sum1[maxn], sum2[maxn];
int dep[maxn];
pair<int,int> edges[maxn];
map<long long, vector<int>> pos;   // for multi-edges: key = (min << 32) | max

void tarjan(int u, int p) {
    tin[u] = low[u] = ++timer;
    for (auto &[v, id] : adj[u]) {
        if (id == p) continue;
        if (!tin[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] == tin[v] && !ismulti[id]) {
                isbridge[id] = true;
            }
        } else {
            low[u] = min(low[u], tin[v]);
        }
    }
}

void dfs_comp(int u, int c) {
    comp[u] = c;
    for (auto &[v, id] : adj[u]) {
        if (comp[v] || isbridge[id]) continue;
        dfs_comp(v, c);
    }
}

void dfs_bctree(int u, int p) {
    dep[u] = dep[p] + 1;
    binlift[u][0] = p;
    for (int i = 1; i < 20; i++) {
        binlift[u][i] = binlift[binlift[u][i-1]][i-1];
    }
    for (int w : bcadj[u]) {
        if (w == p) continue;
        dfs_bctree(w, u);
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int diff = dep[a] - dep[b];
    for (int i = 0; i < 20; i++) {
        if (diff & (1 << i)) a = binlift[a][i];
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (binlift[a][i] != binlift[b][i]) {
            a = binlift[a][i];
            b = binlift[b][i];
        }
    }
    return binlift[a][0];
}

void dfs_sum(int u, int p) {
    for (int w : bcadj[u]) {
        if (w == p) continue;
        dfs_sum(w, u);
        sum1[u] += sum1[w];
        sum2[u] += sum2[w];
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        comp[i] = 0;
        tin[i] = 0;
        dep[i] = 0;
        sum1[i] = sum2[i] = 0;
        bcadj[i].clear();
    }
    timer = 0;
    pos.clear();

    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edges[i] = {a, b};
        long long key = ((long long)min(a,b) << 32) | max(a,b);
        pos[key].push_back(i);
    }

    for (auto &entry : pos) {
        if ((int)entry.second.size() > 1) {
            for (int id : entry.second) {
                ismulti[id] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!tin[i]) tarjan(i, -1);
    }

    int compCnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!comp[i]) {
            compCnt++;
            dfs_comp(i, compCnt);
        }
    }

    for (int i = 1; i <= compCnt; i++) {
        bcadj[i].clear();
        dep[i] = 0;
        for (int j = 0; j < 20; j++) binlift[i][j] = 0;
    }

    for (int i = 1; i <= m; i++) {
        if (!isbridge[i]) continue;
        int a = comp[edges[i].first];
        int b = comp[edges[i].second];
        bcadj[a].push_back(b);
        bcadj[b].push_back(a);
    }

    for (int i = 1; i <= compCnt; i++) {
        if (!dep[i]) {
            dep[i] = 1;
            dfs_bctree(i, 0);
        }
    }

    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        a = comp[a];
        b = comp[b];
        int c = lca(a, b);
        sum1[a]++;
        sum1[c]--;
        sum2[b]++;
        sum2[c]--;
    }

    for (int i = 1; i <= compCnt; i++) {
        if (dep[i] == 1) dfs_sum(i, 0);
    }

    for (int i = 1; i <= m; i++) {
        if (!isbridge[i]) {
            cout << 'B';
            continue;
        }
        int a = comp[edges[i].first];
        int b = comp[edges[i].second];
        bool swapped = false;
        if (dep[a] < dep[b]) {
            swap(a, b);
            swapped = true;
        }
        bool dir;
        if (sum1[a] > 0) dir = true;   // direction is "up" (from child to parent)
        else if (sum2[a] > 0) dir = false;  // direction is "down" (from parent to child)
        else {
            cout << 'B';
            continue;
        }
        // XOR with swapped because we want direction relative to original edge order
        if (dir ^ swapped) cout << 'R';
        else cout << 'L';
    }
    cout << "\n";

    return 0;
}

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