Submission #1247380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247380		khoi	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	2624 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 100000;
int n, m, p;
vector<pii> adj[MAXN+1];      // (neighbor, edge_index)
int parent_edge[MAXN+1];      // edge index to parent in DFS tree
int depth[MAXN+1], low[MAXN+1], tin[MAXN+1], timer;
bool is_tree_edge[200000+5];  // mark edges in DFS tree
char ans[200000+5];           // answer for each edge: 'L','R','B'
int d1[MAXN+1], d2[MAXN+1];  // counters for non-tree edges and queries
pii edges[200000+5];          // original edges (u,v)

// 1) DFS to build tree, compute tin & low, mark tree edges
void dfs1(int u, int pe) {
    tin[u] = low[u] = ++timer;
    for (auto [v, ei] : adj[u]) {
        if (ei == pe) continue;
        if (!tin[v]) {
            is_tree_edge[ei] = true;
            parent_edge[v] = ei;
            dfs1(v, ei);
            low[u] = min(low[u], low[v]);
        } else {
            // back edge
            low[u] = min(low[u], tin[v]);
        }
    }
}

// 2) Post-order DFS to assign edge directions
void dfs2(int u) {
    for (auto [v, ei] : adj[u]) {
        if (!is_tree_edge[ei] || edges[ei].first != u) continue;
        // process child v
        dfs2(v);
        // default B
        ans[ei] = 'B';
        // if subtree sum for non-tree edges is zero, and no pending queries, skip
        if (d1[v] != 0 || d2[v] != 0) {
            // decide direction
            // if queries more exit than enter, orient from v->u else u->v
            bool go_up = (d2[v] > 0);
            if (go_up) ans[ei] = 'R';
            else ans[ei] = 'L';
        }
        // accumulate to parent
        d1[u] += d1[v];
        d2[u] += d2[v];
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    // build DFS tree
    dfs1(1, -1);

    // non-tree edges: mark B and update d1
    for (int i = 0; i < m; i++) {
        if (!is_tree_edge[i]) {
            ans[i] = 'B';
            auto [u, v] = edges[i];
            d1[u]++; d1[v]--;
        }
    }

    // read queries, update d2
    cin >> p;
    while (p--) {
        int a, b;
        cin >> a >> b;
        d2[a]++; d2[b]--;
    }

    // propagate and assign directions
    dfs2(1);

    // output
    for (int i = 0; i < m; i++) cout << ans[i];
    cout << '\n';

    return 0;
}

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