Submission #1259083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259083		maxil	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	99 ms	33608 KiB

oneway

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

static const int MAXN = 200000 + 5;
static const int LOG = 20;

int n, m, p;
int U[MAXN], V[MAXN];

vector<pair<int,int>> g[MAXN]; // undirected multigraph: (to, edge_id)

// --- Tarjan bridges (on multigraph, handles parallel edges & self-loops) ---
int timerDFS, tin[MAXN], low[MAXN];
bool isBridge[MAXN];

void dfs_bridge(int u, int pe) {
    tin[u] = low[u] = ++timerDFS;
    for (auto [v, id] : g[u]) {
        if (id == pe) continue;
        if (!tin[v]) {
            dfs_bridge(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) isBridge[id] = true;
        } else {
            // back-edge / parallel edges (including self-loop) lower low[u]
            low[u] = min(low[u], tin[v]);
        }
    }
}

// --- Compress 2-edge-connected components (contract non-bridge edges) ---
int compOf[MAXN], compCnt;
vector<pair<int,int>> treeAdj[MAXN]; // on components: (neighbor_comp, edge_id) only for bridges

void dfs_comp(int u, int cid) {
    compOf[u] = cid;
    for (auto [v, id] : g[u]) {
        if (compOf[v]) continue;
        if (isBridge[id]) continue; // do not cross bridges when forming component
        dfs_comp(v, cid);
    }
}

// --- LCA on the bridge-forest ---
int up[MAXN][LOG], depthC[MAXN], parentC[MAXN], edgeUp[MAXN]; // edgeUp[child] = bridge edge id to parent

void dfs_lca(int u, int p) {
    parentC[u] = p;
    for (int k = 1; k < LOG; ++k) up[u][k] = up[ up[u][k-1] ][k-1];

    for (auto [v, eid] : treeAdj[u]) if (v != p) {
        depthC[v] = depthC[u] + 1;
        up[v][0] = u;
        edgeUp[v] = eid; // bridge edge id connecting v -> u
        dfs_lca(v, u);
    }
}

int LCA(int a, int b) {
    if (a == 0 || b == 0) return 0;
    if (depthC[a] < depthC[b]) swap(a, b);
    int d = depthC[a] - depthC[b];
    for (int k = LOG-1; k >= 0; --k) if (d & (1<<k)) a = up[a][k];
    if (a == b) return a;
    for (int k = LOG-1; k >= 0; --k) {
        if (up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }
    return up[a][0];
}

// --- Difference arrays on the component-forest ---
int needUp[MAXN], needDown[MAXN]; // per component

void addPath(int a, int b) {
    if (a == b) return; // within same 2ECC ⇒ free (already B)
    int l = LCA(a, b);
    if (l == 0) return; // different connected components (shouldn't happen if input has solution)
    // a -> ... -> l (go up), and l -> ... -> b (go down)
    needUp[a]++;   needUp[l]--;
    needDown[b]++; needDown[l]--;
}

char ans[MAXN]; // answer for each original edge id: 'B','L','R','?'

// propagate needs and decide each bridge edge orientation
void dfs_accumulate(int u, int p) {
    for (auto [v, eid] : treeAdj[u]) if (v != p) {
        dfs_accumulate(v, u);
        needUp[u]   += needUp[v];
        needDown[u] += needDown[v];

        // Decide orientation for this bridge eid along edge (u <-> v)
        // Case 1: only needUp[v] > 0 -> flow v -> u (towards root)
        // Case 2: only needDown[v] > 0 -> flow u -> v (away from root)
        // Case 3: both zero -> unconstrained => 'B'
        // (Both positive cannot happen because a solution is guaranteed.)
        if (needUp[v] > 0 && needDown[v] == 0) {
            // orient comp v -> comp u
            int a = U[eid], b = V[eid];
            int ca = compOf[a], cb = compOf[b];
            // If original direction a->b corresponds to (v->u), print 'R', else 'L'
            if (ca == v && cb == u) ans[eid] = 'R';
            else                     ans[eid] = 'L';
        } else if (needDown[v] > 0 && needUp[v] == 0) {
            // orient comp u -> comp v
            int a = U[eid], b = V[eid];
            int ca = compOf[a], cb = compOf[b];
            if (ca == u && cb == v) ans[eid] = 'R';
            else                     ans[eid] = 'L';
        } else {
            // unconstrained
            if (ans[eid] == 0) ans[eid] = 'B';
        }
    }
}

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        int a, b; cin >> a >> b;
        U[i] = a; V[i] = b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    // 1) Tarjan to find bridges (graph can be disconnected)
    for (int i = 1; i <= n; ++i) if (!tin[i]) dfs_bridge(i, -1);

    // 2) Compress 2-edge-connected components
    for (int i = 1; i <= n; ++i) if (!compOf[i]) dfs_comp(i, ++compCnt);

    // Initialize answers: non-bridge edges are inside cycles ⇒ 'B'
    for (int i = 1; i <= m; ++i) if (!isBridge[i]) ans[i] = 'B';

    // 3) Build the bridge-forest over components, store edge id on the adjacency
    for (int i = 1; i <= m; ++i) if (isBridge[i]) {
        int ca = compOf[U[i]], cb = compOf[V[i]];
        treeAdj[ca].push_back({cb, i});
        treeAdj[cb].push_back({ca, i});
    }

    // 4) LCA preprocess on each tree in the forest
    // up[*][*] already 0; set roots wherever parentC==0
    for (int r = 1; r <= compCnt; ++r) {
        if (parentC[r] == 0) {
            up[r][0] = 0; depthC[r] = 0; edgeUp[r] = 0;
            dfs_lca(r, 0);
        }
    }

    // 5) Read reachability pairs and add path constraints on component-forest
    cin >> p;
    for (int i = 0; i < p; ++i) {
        int x, y; cin >> x >> y;
        int cx = compOf[x], cy = compOf[y];
        if (cx == cy) continue; // already satisfied within 2ECC
        addPath(cx, cy);
    }

    // 6) Accumulate needs and determine each bridge orientation
    for (int r = 1; r <= compCnt; ++r) {
        if (parentC[r] == 0) dfs_accumulate(r, 0);
    }

    // Any remaining bridge without constraint => 'B'
    for (int i = 1; i <= m; ++i) if (isBridge[i] && ans[i] == 0) ans[i] = 'B';

    // 7) Output the string
    for (int i = 1; i <= m; ++i) cout << ans[i];
    cout << '\n';
    return 0;
}

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