52182023-04-22 20:23:46Valaki2Turista járatokcpp14Wrong answer 10/100170ms92596 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() != prv_id) {
                    comp[s.top()] = comp_cnt;
                    s.pop();
                }
            }
        }
    }
    for(const edge &e : graph[cur]) {
        if(e.id != prv_id && comp[e.id] == 0) {
            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
1Accepted9ms22552 KiB
2Wrong answer17ms24840 KiB
subtask20/10
3Wrong answer9ms22984 KiB
4Wrong answer12ms23244 KiB
5Accepted12ms23584 KiB
6Accepted12ms23676 KiB
7Accepted10ms24024 KiB
subtask310/10
8Accepted12ms24112 KiB
9Accepted12ms24328 KiB
10Accepted12ms24660 KiB
11Accepted12ms24724 KiB
12Accepted14ms25492 KiB
subtask40/10
13Accepted16ms26784 KiB
14Accepted12ms25048 KiB
15Wrong answer12ms25260 KiB
16Wrong answer12ms25364 KiB
17Accepted153ms80600 KiB
18Accepted57ms40920 KiB
19Wrong answer75ms46656 KiB
20Wrong answer54ms43400 KiB
subtask50/10
21Wrong answer17ms34680 KiB
22Accepted9ms32940 KiB
23Wrong answer9ms32976 KiB
24Accepted12ms33040 KiB
25Accepted101ms68924 KiB
26Accepted17ms38112 KiB
27Accepted17ms38532 KiB
subtask60/60
28Accepted10ms36740 KiB
29Wrong answer9ms36660 KiB
30Wrong answer13ms36880 KiB
31Wrong answer14ms37004 KiB
32Wrong answer13ms37260 KiB
33Wrong answer14ms37860 KiB
34Wrong answer18ms38864 KiB
35Wrong answer18ms39176 KiB
36Wrong answer18ms39184 KiB
37Accepted170ms92596 KiB
38Accepted59ms52848 KiB
39Accepted54ms53820 KiB
40Accepted59ms54920 KiB
41Wrong answer54ms55684 KiB
42Wrong answer54ms56496 KiB
43Accepted54ms57656 KiB
44Wrong answer54ms58480 KiB
45Wrong answer71ms64256 KiB
46Wrong answer54ms60900 KiB
47Wrong answer54ms61448 KiB
48Wrong answer57ms62460 KiB
49Accepted54ms63548 KiB
50Accepted59ms64380 KiB