Submission #1185919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185919		tin_le	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	70 ms	32840 KiB

oneway

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

const int maxn = 2e5 + 5;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

struct Tarjan {
    int n, m, timer, comp;
    vi tin, low, scc, dp, belong, vis;
    vvpii graph, adj;
    vi bridges;
    string ans;
    stack<int> st;
    Tarjan(const vvpii &graph, int edges_size) : n(graph.size()), m(edges_size), timer(0), comp(0) {
        this->graph = graph;
        tin.resize(n, 0); low.resize(n, 0); scc.resize(n, 0); belong.resize(n, 0);
        dp.resize(n, 0); vis.resize(n, 0);
        bridges.resize(m, 0);
        ans.resize(m + 1, 'B');
        for (int i = 0; i < n; i++) {
            if (!tin[i]) dfs(i, -1);
        }
    }
    void dfs(int node, int par) {
        st.push(node);
        tin[node] = low[node] = ++timer;
        for (auto &pr : graph[node]) {
            int nei = pr.first, id = pr.second;
            if (id == par) continue;
            if (!tin[nei]) {
                dfs(nei, id);
                low[node] = min(low[node], low[nei]);
                if (low[nei] > tin[node]) {
                    bridges[id] = 1;
                }
            } else {
                low[node] = min(low[node], tin[nei]);
            }
        }
        if (low[node] == tin[node]) {
            while (true) {
                int u = st.top(); st.pop();
                scc[u] = node;
                belong[u] = comp;
                if (u == node) break;
            }
            comp++;
        }
    }
    pair<int, vvpii> compress_graph(vpii &edges) {
        vi degree(comp, 0);
        vvpii G(comp);
        for (int i = 0; i < m; i++) {
            if (!bridges[i]) continue;
            auto &e = edges[i];
            int u = belong[e.first], v = belong[e.second];
            if (u == v) continue;
            e.first = u; e.second = v;
            G[u].push_back({v, i});
            G[v].push_back({u, i});
            degree[u]++; degree[v]++;
        }
        int root = -1;
        for (int i = 0; i < comp; i++) {
            if (degree[i] == 1) { root = i; break; }
        }
        return {root, G};
    }
    void dfs2(int x, int par, int last, const vpii &edges) {
        vis[x] = 1;
        for (auto &pr : adj[x]) {
            int nei = pr.first, id = pr.second;
            if (nei == par) continue;
            dfs2(nei, x, id, edges);
            dp[x] += dp[nei];
        }
        if (last == -1 || dp[x] == 0) return;
        if (dp[x] > 0)
            ans[last] = (x == edges[last].first ? 'R' : 'L');
        else
            ans[last] = (x == edges[last].second ? 'R' : 'L');
    }
};

void solve(){
    int n, m; 
    cin >> n >> m;
    vvpii graph(n);
    vpii edges(m);
    for (int i = 0; i < m; i++){
        int u, v; 
        cin >> u >> v; 
        u--; v--;
        edges[i] = {u, v};
        graph[u].push_back({v, i});
        graph[v].push_back({u, i});
    }
    Tarjan T(graph, m);
    int q; 
    cin >> q;
    while(q--){
        int u, v; 
        cin >> u >> v; 
        u--; v--;
        T.dp[T.belong[u]]++;
        T.dp[T.belong[v]]--;
    }
    auto compData = T.compress_graph(edges);
    int root = compData.first;
    T.adj = compData.second;
    for (int i = 0; i < T.comp; i++){
        if (!T.vis[i]) T.dfs2(i, -1, -1, edges);
    }
    string res;
    for (int i = 0; i < m; i++) res.push_back(T.ans[i]);
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    solve();
}

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