제출 #1326364

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

oneway

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

void HossamMourad();

void fokakmneeee() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int> > > adj(n + 1);
    vector<pair<int, int> > edges;
    vector<tuple<int, int, int> > bridges;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        edges.push_back({u, v});
    }

    vector<bool> vis(n + 1), is_bridge(m + 1);
    vector<int> mn(n + 1, 1e9), dep(n + 1, 0);

    auto dfs = [&](auto &&dfs, int u, int ind)-> void {
        vis[u] = true;
        mn[u] = min(mn[u], dep[u]);

        for (auto [v, idx]: adj[u]) {
            if (idx == ind) continue;
            if (!vis[v]) {
                dep[v] = dep[u] + 1;
                dfs(dfs, v, idx);
                mn[u] = min(mn[u], mn[v]);
                if (mn[v] > dep[u]) {
                    is_bridge[idx] = true;
                    bridges.push_back({u, v, idx});
                }
            } else {
                mn[u] = min(mn[u], dep[v]);
            }
        }
    };
    dfs(dfs, 1, -1);
    vis = vector<bool>(n + 1, false);
    vector<int> comp(n + 1), freq(n + 1);
    int cmp = 1;

    auto dfs2 = [&](auto &&dfs2, int u)-> void {
        vis[u] = true;
        comp[u] = cmp;
        freq[cmp]++;
        for (auto [v, idx]: adj[u]) {
            if (!vis[v] && !is_bridge[idx]) {
                dfs2(dfs2, v);
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs2(dfs2, i);
            cmp++;
        }
    }


    vector<bool> done(m + 1);
    auto dfs3 = [&](auto &&dfs3, int u, int ind)-> void {
        vis[u] = true;
        for (auto [v, idx]: adj[u]) {
            if (idx == ind) continue;
            if (!vis[v] && !is_bridge[idx]) {
                if (!done[idx]) {
                    edges[idx] = {u, v};
                    done[idx] = true;
                }
                dfs3(dfs3, v, idx);
            } else if (!is_bridge[idx]) {
                if (!done[idx]) {
                    edges[idx] = {u, v};
                    done[idx] = true;
                }
            }
        }
    };

    vis = vector<bool>(n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs3(dfs3, i, -1);
        }
    }

    vector<vector<pair<int, int> > > bridge_tree(cmp + 1);
    for (auto [v, u, idx]: bridges) {
        bridge_tree[comp[u]].push_back({comp[v], idx});
        bridge_tree[comp[v]].push_back({comp[u], idx});
    }

    int st, en;
    string ans(m, 'B');
    vis = vector<bool>(n + 1, false);

    auto dfs4 = [&](auto &&dfs4, int u)-> bool {
        vis[u] = true;
        if (u == comp[en]) return true;
        bool found = false;
        for (auto [v, idx]: bridge_tree[u]) {
            if (!vis[v]) {
                if (dfs4(dfs4, v)) {
                    found = true;
                    if (comp[edges[idx].first] != u) {
                        ans[idx] = 'L';
                    } else {
                        ans[idx] = 'R';
                    }
                }
            }
        }
        return found;
    };

    int q;
    cin >> q;
    while (q--) {
        vis = vector<bool>(cmp + 1, false);
        cin >> st >> en;
        dfs4(dfs4, comp[st]);
    }
    cout << ans;
}


int32_t main() {
    HossamMourad();
    int t = 1;
    // cin >> t;
    while (t--) {
        fokakmneeee();
        if (t) cout << "\n";
    }

    return 0;
}

void HossamMourad() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
// #if ONLINE_JUDGE
//     // freopen("airport.in", "r", stdin);
//     // freopen("Output.txt", "w", stdout);
// #else
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
}

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