1240 2022. 03. 28 16:21:49 k_balint Turista járatok cpp14 Elfogadva 100/100 181ms 78188 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=40004;

struct edge{
    int v,id;
    edge(int vv, int i){
        v=vv; id=i;
    }
    edge(){
        v=id=0;
    }
};

int n,m,k;
vector<edge> adj[c];
int t[c],l[c];
bool used[10*c];
stack<int> s;
int tt; int cnt;
vector<int> comp[3*c];
int cut[c];
int ecmp[10*c];
bool good[3*c];
bool cut_cmp[3*c];

void new_comp(int id){
    while(!s.empty() && s.top() != id){
        int cur=s.top();
        s.pop();
        if(cur<=k) good[cnt]=1;
        ecmp[cur]=cnt;
        comp[cnt].push_back(cur);
    }

    if(!s.empty()){
        int cur=s.top();
        s.pop();
        if(cur<=k) good[cnt]=1;
        ecmp[cur]=cnt;
        comp[cnt].push_back(cur);
    }

    ++cnt;
}

vector<int> tree[3*c];
vector<edge> edges;

void dfs(int v, int p){
    t[v]=l[v]=tt++;
    bool children=0;

    for(edge x:adj[v]){
        if(x.id==p) continue;
        if(!used[x.id]){
            used[x.id]=1;
            s.push(x.id);
        }

        if(!t[x.v]){
            dfs(x.v,x.id);
            l[v]=min(l[v],l[x.v]);

            if(v==1?children:l[x.v]>=t[v]){
                if(!cut[v]){
                    cut_cmp[cnt]=1;
                    cut[v]=cnt;
                    comp[cnt].push_back(v); ++cnt;
                }
                tree[cut[v]].push_back(cnt);
                tree[cnt].push_back(cut[v]);
                new_comp(x.id);
            }

            children=1;
        }
        else l[v]=min(l[v],t[x.v]);
    }

    if(cut[v] && p!=0){
        edges.push_back(edge(cut[v],p));
    }

    if(v==1 && !s.empty()){
        if(cut[v]){
            tree[cut[v]].push_back(cnt);
            tree[cnt].push_back(cut[v]);
        }
        new_comp(-1);
    }
}

bool vis[3*c];
void dfs2(int v, bool g){
    vis[v]=1; good[v]|=g;
    for(int x:tree[v]){
        if(!vis[x]){
            dfs2(x,good[v]);
        }
    }
}

bool ans[c];
edge edg[10*c];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        edg[i]=edge(a,b);
        adj[a].push_back(edge(b,i));
        adj[b].push_back(edge(a,i));
    }

    tt=1; cnt=1;
    dfs(1,0);

    for(edge x:edges){
        tree[x.v].push_back(ecmp[x.id]);
        tree[ecmp[x.id]].push_back(x.v);
    }

    if(adj[1].empty()){
        cout << 0 << endl;
        return 0;
    }

    if(!cut[1]) dfs2(ecmp[adj[1][0].id],0);
    else dfs2(cut[1],0);

    for(int i=1;i<cnt;i++){
        if(!good[i]) continue;
        if(cut_cmp[i]){
            ans[comp[i][0]]=1;
            continue;
        }

        for(int x:comp[i]){
            int a=edg[x].v;
            int b=edg[x].id;
            if(!cut[a]) ans[a]=1;
            if(!cut[b]) ans[b]=1;
        }
    }

    ans[1]=0;

    int ans2=0;
    for(int i=1;i<=n;i++){
        if(ans[i]) ++ans2;
    }

    cout << ans2 << '\n';

    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout << i << ' ';
        }
    }

    cout << endl;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 12ms 21256 KiB
2 Elfogadva 19ms 23268 KiB
subtask2 10/10
3 Elfogadva 10ms 21460 KiB
4 Elfogadva 10ms 21472 KiB
5 Elfogadva 9ms 21468 KiB
6 Elfogadva 12ms 21476 KiB
7 Elfogadva 10ms 21488 KiB
subtask3 10/10
8 Elfogadva 9ms 21484 KiB
9 Elfogadva 9ms 21488 KiB
10 Elfogadva 9ms 21508 KiB
11 Elfogadva 10ms 21784 KiB
12 Elfogadva 14ms 23212 KiB
subtask4 10/10
13 Elfogadva 17ms 24816 KiB
14 Elfogadva 9ms 21656 KiB
15 Elfogadva 10ms 21876 KiB
16 Elfogadva 10ms 21960 KiB
17 Elfogadva 181ms 67036 KiB
18 Elfogadva 59ms 34904 KiB
19 Elfogadva 76ms 38908 KiB
20 Elfogadva 56ms 37216 KiB
subtask5 10/10
21 Elfogadva 17ms 30780 KiB
22 Elfogadva 10ms 29044 KiB
23 Elfogadva 12ms 29068 KiB
24 Elfogadva 12ms 29220 KiB
25 Elfogadva 115ms 56260 KiB
26 Elfogadva 17ms 33576 KiB
27 Elfogadva 17ms 33724 KiB
subtask6 60/60
28 Elfogadva 10ms 32372 KiB
29 Elfogadva 10ms 32408 KiB
30 Elfogadva 12ms 32640 KiB
31 Elfogadva 13ms 32756 KiB
32 Elfogadva 13ms 33008 KiB
33 Elfogadva 17ms 33288 KiB
34 Elfogadva 17ms 34332 KiB
35 Elfogadva 17ms 34484 KiB
36 Elfogadva 17ms 34632 KiB
37 Elfogadva 181ms 78188 KiB
38 Elfogadva 54ms 45908 KiB
39 Elfogadva 54ms 46960 KiB
40 Elfogadva 56ms 47844 KiB
41 Elfogadva 57ms 48768 KiB
42 Elfogadva 54ms 49500 KiB
43 Elfogadva 57ms 50452 KiB
44 Elfogadva 56ms 51448 KiB
45 Elfogadva 83ms 55568 KiB
46 Elfogadva 59ms 53724 KiB
47 Elfogadva 57ms 54656 KiB
48 Elfogadva 59ms 55344 KiB
49 Elfogadva 57ms 56380 KiB
50 Elfogadva 65ms 57264 KiB