제출 #1326139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326139		hossammourad	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 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);
    vector<int> mn(n + 1, 1e9), dep(n + 1);

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

        for (auto [v, idx]: adj[u]) {
            if (v == p) continue;
            if (!vis[v]) {
                dfs(dfs, v, u);
                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, 0);
    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 p)-> void {
        vis[u] = true;
        for (auto [v, idx]: adj[u]) {
            if (v == p) continue;
            if (!vis[v] && !is_bridge[idx]) {
                if (!done[idx]) {
                    edges[idx] = {u, v};
                    done[idx] = true;
                }
                dfs3(dfs3, v, u);
            } 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)-> void {
        vis[u] = true;
        if (u == comp[en]) return;
        for (auto [v, idx]: bridge_tree[u]) {
            if (!vis[v]) {
                if (comp[edges[idx].first] != u) {
                    ans[idx] = 'L';
                } else {
                    ans[idx] = 'R';
                }
                dfs4(dfs4, v);
            }
        }
    };

    int q;
    cin >> q;
    while (q--) {
        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
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'void HossamMourad()':
oneway.cpp:147:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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