Submission #1257120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257120		nikaa123	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3095 ms	320 KiB

oneway

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

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vpii = vector<pii>;

const int MAXN = 1e5 + 5;
const int LOG = 18;
const int INF = INT_MAX;

int n, m, q;
vector<vpii> graph, bridgeTree;
vi visited, low, tin, tout, component, parentEdge;
vector<vector<int>> up;
vector<bool> isBridge;
vector<char> edgeDir;
vector<pii> edges;

int timer = 0;
int compId = 0;

// DFS to find bridges using Tarjan's algorithm
void findBridges(int u, int p) {
    visited[u] = 1;
    tin[u] = low[u] = timer++;
    for (auto &[v, id] : graph[u]) {
        if (v == p) continue;
        if (visited[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            findBridges(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) {
                isBridge[id] = true;
                bridgeTree[u].emplace_back(v, id);
                bridgeTree[v].emplace_back(u, id);
            }
        }
    }
}

// DFS to build components excluding bridges
void buildComponent(int u) {
    visited[u] = 1;
    component[u] = compId;
    for (auto &[v, id] : graph[u]) {
        if (visited[v] || isBridge[id]) continue;
        buildComponent(v);
    }
}

// DFS to prepare LCA binary lifting
void dfsLCA(int u, int p) {
    tin[u] = timer++;
    up[u][0] = p;
    visited[u] = 1;

    for (int i = 1; i < LOG; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }

    for (auto &[v, id] : bridgeTree[u]) {
        if (v == p) continue;
        parentEdge[v] = id;
        dfsLCA(v, u);
    }

    tout[u] = timer++;
}

bool isAncestor(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (isAncestor(a, b)) return a;
    if (isAncestor(b, a)) return b;

    for (int i = LOG - 1; i >= 0; --i) {
        if (!isAncestor(up[a][i], b))
            a = up[a][i];
    }
    return up[a][0];
}

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    int N = 2 * n + 5;    // total nodes including components
    int M = 2 * m + 5;    // total edges (or edge ids)

    graph.assign(N, {});
    bridgeTree.assign(N, {});
    visited.assign(N, 0);
    low.assign(N, 0);
    tin.assign(N, 0);
    tout.assign(N, 0);
    component.assign(N, 0);
    parentEdge.assign(N, 0);
    up.assign(N, vector<int>(LOG, 0));

    isBridge.assign(M, false);
    edgeDir.assign(M, 'B');
    edges.assign(M,{});

    for (int i = 1; i <= m; ++i) {
        int a, b; cin >> a >> b;
        graph[a].emplace_back(b, i);
        graph[b].emplace_back(a, i);
        edges[i] = {a, b};
    }

    timer = 0;
    fill(visited.begin(), visited.end(), 0);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i])
            findBridges(i, -1);
    }

    // Build components by excluding bridges
    fill(visited.begin(), visited.end(), 0);
    compId = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            ++compId;
            buildComponent(i);
        }
    }

    // Build bridge tree connections for components
    // Add edges between nodes and their components if necessary
    vector<vpii> newGraph(compId + 1);
    for (int i = 1; i <= m; ++i) {
        int a = edges[i].first;
        int b = edges[i].second;
        if (!isBridge[i]) {
            // Connect node to its component if different
            if (component[a] != component[b]) {
                newGraph[component[a]].emplace_back(component[b], 0);
                newGraph[component[b]].emplace_back(component[a], 0);
            }
        }
    }
    // Replace bridgeTree by component graph (if needed)
    // But since original code uses v1 with both nodes and components, you might want to adjust this logic
    // For now, assume we build LCA on original nodes with bridge edges only:
    bridgeTree.clear();
    bridgeTree.assign(n + 1, {});
    for (int i = 1; i <= m; ++i) {
        if (isBridge[i]) {
            auto [a, b] = edges[i];
            bridgeTree[a].emplace_back(b, i);
            bridgeTree[b].emplace_back(a, i);
        }
    }

    // Prepare LCA on bridgeTree
    timer = 0;
    fill(visited.begin(), visited.end(), 0);
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfsLCA(i, i);
        }
    }

    cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        int ancestor = lca(a, b);

        // Traverse path from a to ancestor
        int cur = a;
        while (cur != ancestor) {
            int p = up[cur][0];
            pii edge = {cur, p};
            if (edges[parentEdge[cur]] == edge)
                edgeDir[parentEdge[cur]] = 'R';
            else
                edgeDir[parentEdge[cur]] = 'L';
            cur = p;
        }

        // Traverse path from b to ancestor
        cur = b;
        while (cur != ancestor) {
            int p = up[cur][0];
            pii edge = {p, cur};
            if (edges[parentEdge[cur]] == edge)
                edgeDir[parentEdge[cur]] = 'R';
            else
                edgeDir[parentEdge[cur]] = 'L';
            cur = p;
        }
    }

    for (int i = 1; i <= m; ++i)
        cout << edgeDir[i];
    cout << '\n';
}

int main() {
    solve();
    return 0;
}

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