제출 #1247382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247382		khoi	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	2624 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
static const int MAXN = 100000;

int n, m, p, timer;
vector<pii> adj[MAXN+1];       // (neighbor, edge_id)
int tin[MAXN+1], low[MAXN+1];  // Tarjan arrays
bool isTreeEdge[200000+5];
char ans[200000+5];
pii edges[200000+5];

// 1) Build DFS‐tree, compute tin/low, mark tree‐edges
void dfs1(int u, int pe) {
    tin[u] = low[u] = ++timer;
    for (auto [v, eid] : adj[u]) {
        if (eid == pe) continue;
        if (!tin[v]) {
            isTreeEdge[eid] = true;
            dfs1(v, eid);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], tin[v]);
        }
    }
}

// 2) dfs2 returns net flow through node u
//    +x means x more paths need to go upward through parent
//    –x means x more paths come down from parent into this subtree
int dfs2(int u, int pe, vector<int>& cnt) {
    int subtotal = cnt[u];

    for (auto [v, eid] : adj[u]) {
        if (!isTreeEdge[eid] || eid == pe) continue;
        // only traverse DOWN the tree, skipping the reverse link
        int childFlow = dfs2(v, eid, cnt);

        // decide ans[eid] by childFlow:
        //   0  → no path crosses → 'B'
        //  >0  → flow goes UP (v→u) → orient accordingly
        //  <0  → flow goes DOWN (u→v)
        if (childFlow == 0) {
            ans[eid] = 'B';
        } else if (childFlow > 0) {
            // child→parent
            // if edges[eid] == (u,v) in input order: L = u→v, R = v→u
            ans[eid] = (edges[eid].first == u ? 'R' : 'L');
        } else {
            // parent→child
            ans[eid] = (edges[eid].first == u ? 'L' : 'R');
        }

        subtotal += childFlow;
    }

    return subtotal;
}

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);
    }

    // 1) Build tree + lowlinks
    dfs1(1, -1);

    // 2) Prepare a counter of how many query‐paths start/end at each node
    vector<int> cnt(n+1, 0);

    // Non‐tree edges are always 'B' and contribute +1/–1 to their endpoints
    for(int i = 0; i < m; i++){
        if(!isTreeEdge[i]){
            ans[i] = 'B';
            auto [u,v] = edges[i];
            cnt[u]++; 
            cnt[v]--;
        }
    }

    // Read the p query‐pairs (a→b)
    cin >> p;
    while(p--){
        int a,b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]--;
    }

    // 3) dfs2 from root 1 — it returns the net flow for its component
    dfs2(1, -1, cnt);

    // 4) Print
    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