52192023-04-22 21:36:48Valaki2Turista járatokcpp14Wrong answer 30/100158ms71412 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

struct edge {
    int from, to, id;
};

const int maxn = 40'000;
const int maxm = 400'000;
const int root = 1;
const int maxc = maxm; // actually maxn should be enough!!!!!

int n, m, k;
vector<edge> graph[1 + maxn];
pii edges[1 + maxm];

/*bool special(const edge &e) {
    return e.id <= k;
}*/

int t;
int dep[1 + maxn];
int low[1 + maxn];
bool cut[1 + maxn];

bool vis_low[1 + maxn];

void dfs_low(int cur, int par) {
    t++;
    dep[cur] = t;
    low[cur] = t;
    vis_low[cur] = true;
    int cnt = 0;
    int lowcheck = 0;
    for(const edge &e : graph[cur]) {
        int nei = e.to;
        if(!vis_low[nei]) {
            cnt++;
            dfs_low(nei, cur);
            low[cur] = min(low[cur], low[nei]);
            lowcheck = max(lowcheck, low[nei]);
        } else if(nei != par) {
            low[cur] = min(low[cur], dep[nei]);
        }
    }
    if((par == -1 && cnt > 1) || ((par != -1) && (lowcheck >= dep[cur]) && (cnt > 0))) {
        cut[cur] = true;
    }
}

stack<int> s;
int comp_cnt;
int start[1 + maxc];
int comp[1 + maxm];
int nodes_comp[1 + maxn];

bool vis_bcc[1 + maxn];

void dfs_bcc(int cur, int prv_id) {
    vis_bcc[cur] = true;
    for(const edge &e : graph[cur]) {
        if(!vis_bcc[e.to]) {
            s.push(e.id);
            dfs_bcc(e.to, e.id);
            if((low[e.to] >= dep[cur]) && (cut[cur] || cur == root)) {
                comp_cnt++;
                start[comp_cnt] = cur;
                while(!s.empty() && s.top() != e.id) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
                if(!s.empty()) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
            }
        } else if(e.id != prv_id && dep[e.to] < low[cur]) {
            s.push(e.id);
        }
    }
}

vector<int> tree[1 + maxc];
bool has[1 + maxc];

void dfs_has(int cur, bool have) {
    if(have) {
        has[cur] = true;
    }
    have = has[cur];
    for(int nei : tree[cur]) {
        dfs_has(nei, have);
    }
}

void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb({a, b, i});
        graph[b].pb({b, a, i});
        edges[i] = mp(a, b);
    }
    dfs_low(root, -1);
    dfs_bcc(root, -1);
    for(int i = 1; i <= m; i++) {
        if(comp[i] != 0) {
            if(start[comp[i]] != edges[i].fi) {
                nodes_comp[edges[i].fi] = comp[i];
            }
            if(start[comp[i]] != edges[i].se) {
                nodes_comp[edges[i].se] = comp[i];
            }
        }
    }
    for(int i = 1; i <= comp_cnt; i++) {
        tree[nodes_comp[start[i]]].pb(i);
    }
    for(int i = 1; i <= k; i++) {
        has[comp[i]] = true;
    }
    dfs_has(0, false);
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(has[nodes_comp[i]]) {
            ans.pb(i);
        }
    }
    cout << ans.size() << "\n";
    for(int x : ans) {
        cout << x << " ";
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted13ms22548 KiB
2Wrong answer19ms24936 KiB
subtask210/10
3Accepted10ms23064 KiB
4Accepted9ms23016 KiB
5Accepted9ms23280 KiB
6Accepted9ms23492 KiB
7Accepted9ms23708 KiB
subtask30/10
8Wrong answer9ms23664 KiB
9Accepted9ms23780 KiB
10Accepted9ms23868 KiB
11Accepted9ms24092 KiB
12Accepted14ms24964 KiB
subtask410/10
13Accepted17ms26144 KiB
14Accepted12ms24540 KiB
15Accepted13ms24728 KiB
16Accepted13ms25056 KiB
17Accepted157ms70784 KiB
18Accepted57ms34784 KiB
19Accepted68ms38468 KiB
20Accepted57ms34912 KiB
subtask510/10
21Accepted17ms27064 KiB
22Accepted12ms25516 KiB
23Accepted12ms25632 KiB
24Accepted10ms25568 KiB
25Accepted87ms55556 KiB
26Accepted16ms27284 KiB
27Accepted17ms27252 KiB
subtask60/60
28Accepted10ms25548 KiB
29Wrong answer10ms25696 KiB
30Wrong answer13ms25900 KiB
31Wrong answer14ms26264 KiB
32Wrong answer14ms26344 KiB
33Wrong answer16ms26472 KiB
34Wrong answer17ms27660 KiB
35Wrong answer17ms27600 KiB
36Wrong answer17ms27600 KiB
37Accepted158ms71412 KiB
38Accepted57ms35540 KiB
39Accepted57ms35400 KiB
40Accepted54ms35652 KiB
41Accepted57ms35640 KiB
42Accepted57ms35608 KiB
43Accepted56ms35608 KiB
44Accepted54ms35596 KiB
45Accepted68ms39372 KiB
46Accepted54ms35644 KiB
47Accepted57ms35816 KiB
48Accepted57ms35620 KiB
49Accepted57ms35620 KiB
50Accepted56ms35624 KiB