162702025-04-19 10:43:39szilTurista járatokcpp17Wrong answer 30/100180ms42748 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 500'001;

vector<pair<int, int>> g[MAXN];
vector<int> bct[MAXN];
vector<pair<int, int>> edges;
vector<int> st;
vector<vector<int>> comps;
bool is_cutpoint[MAXN], is_good[MAXN];
int tin[MAXN], low[MAXN], cid[MAXN], tin2[MAXN], timer = 1, th;
map<int, vector<int>> id_to_nodes;
vector<int> ans;

void dfs(int u, int p = -1) {
    int cnt = 0;
    tin[u] = low[u] = timer++;
    st.emplace_back(u);
    for (auto [v, _] : g[u]) {
        if (v == p) continue;
        if (tin[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= tin[u]) {
                is_cutpoint[u] = (tin[u] > 1 || tin[v] > 2);
                comps.push_back({u});
                while (st.back() != u) {
                    comps.back().push_back(st.back());
                    st.pop_back();
                }
            }
        }
    }
}

void dfs2(int u, int p = -1) {
    tin2[u] = timer++;
    for (int v : bct[u]) {
        if (v != p) {
            dfs2(v, u);
        }
    }
}

void dfs3(int u, int p = -1, bool g = false) {
    if (is_good[u]) g = 1;

    if (g) {
        for (int c : id_to_nodes[u]) {
            if (c != 1) ans.emplace_back(c);
        }
    }

    for (int v : bct[u]) {
        if (v != p) dfs3(v, u, g);
    }
}

void solve() {
    int n, m, k; cin >> n >> m >> k;

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

    dfs(1);
    int cc = 0;
    for (int i = 1; i <= n; i++) {
        if (is_cutpoint[i]) {
            cid[i] = ++cc;
            id_to_nodes[cc] = {i};
        }
    }

    th = cc;

    for (auto &vec : comps) {
        int id = ++cc;
        sort(vec.begin(), vec.end());
        id_to_nodes[id] = {};
        for (int u : vec) {
            for (auto [v, idx] : g[u]) {
                if (idx < k && binary_search(vec.begin(), vec.end(), v)) {
                    is_good[id] = 1;
                }
            }
            if (is_cutpoint[u]) {
                bct[id].emplace_back(cid[u]);
                bct[cid[u]].emplace_back(id);
            } else {
                id_to_nodes[id].emplace_back(u);
                cid[u] = id;
            }
        }
    }

    dfs2(cid[1]);
    for (int i = 0; i < k; i++) {
        auto [u, v] = edges[i];
        if (tin2[cid[u]] < tin2[cid[v]]) is_good[cid[v]] = 1;
        else is_good[cid[u]] = 1;
    }

    dfs3(cid[1]);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    cout << ans.size() << "\n";
    for (int u : ans) cout << u << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted18ms23860 KiB
2Accepted34ms25140 KiB
subtask210/10
3Accepted25ms23860 KiB
4Accepted19ms23948 KiB
5Accepted26ms23864 KiB
6Accepted19ms23860 KiB
7Accepted18ms23860 KiB
subtask310/10
8Accepted25ms23860 KiB
9Accepted19ms23872 KiB
10Accepted19ms23816 KiB
11Accepted26ms24116 KiB
12Accepted26ms25396 KiB
subtask410/10
13Accepted39ms26992 KiB
14Accepted19ms23860 KiB
15Accepted25ms23860 KiB
16Accepted20ms24140 KiB
17Accepted173ms42644 KiB
18Accepted74ms28580 KiB
19Accepted83ms29860 KiB
20Accepted68ms28536 KiB
subtask50/10
21Accepted35ms25140 KiB
22Accepted19ms23860 KiB
23Wrong answer20ms23860 KiB
24Accepted25ms23872 KiB
25Accepted108ms34360 KiB
26Accepted26ms24640 KiB
27Accepted26ms24632 KiB
subtask60/60
28Accepted20ms23860 KiB
29Accepted20ms23860 KiB
30Accepted27ms24116 KiB
31Accepted28ms24116 KiB
32Wrong answer23ms24372 KiB
33Accepted24ms24372 KiB
34Accepted28ms25136 KiB
35Accepted34ms25296 KiB
36Accepted28ms25140 KiB
37Accepted180ms42748 KiB
38Accepted74ms28736 KiB
39Accepted67ms28576 KiB
40Accepted67ms28840 KiB
41Accepted67ms28736 KiB
42Accepted76ms28584 KiB
43Accepted67ms28584 KiB
44Accepted75ms28584 KiB
45Accepted94ms29860 KiB
46Accepted67ms28580 KiB
47Accepted67ms28584 KiB
48Accepted67ms28688 KiB
49Accepted72ms28596 KiB
50Accepted65ms28756 KiB