161852025-04-13 17:56:22lacitoTurista járatokcpp17Wrong answer 20/100104ms26288 KiB
#include<bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define gc getchar_unlocked

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

struct el {
    int from,to,ind;
};

const int MAXN=50001;
const int MAXM=600001;

bool isc[MAXM];
vector<el> adj[MAXN];

int st[MAXN], par[MAXN];
int ans[MAXN];
int active[MAXN];
void dfs(int x, bool have=false) {
    st[x]=1;
    if(have) ans[x]=1;
    for(auto i:adj[x]) {
        if(par[x]!=i.to) isc[i.ind]|=have;
        
        if(!st[i.to]) {
            bool volt=isc[i.ind]==false;
            par[i.to]=x;
            active[x]=i.ind;
            dfs(i.to, have|isc[i.ind]);
            if(volt && isc[i.ind]) {
                st[i.to]=0;
                dfs(i.to, true);
            }
            active[x]=-1;
        }else if(have && par[x]!=i.to) {
            isc[active[i.to]]=true;
        }
    }
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m,k;
    n=getint<int>();
    m=getint<int>();
    k=getint<int>();
    for(int i=0;i<m;++i) {
        int a,b;
        a=getint<int>();
        b=getint<int>();
        isc[i]=i<k;
        adj[a].push_back(el{a,b,i});
        adj[b].push_back(el{b,a,i});
    }
    
    dfs(1);
    for(int i=1;i<=n;++i) st[i]=0;
    dfs(1);
    
    
    vector<int> res;
    for(int i=1;i<=n;++i) if(ans[i]) res.push_back(i);
    cout<<res.size()<<"\n";
    for(auto i:res) cout<<i<<" ";
    cout<<"\n";
    
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1616 KiB
2Accepted6ms2368 KiB
subtask210/10
3Accepted2ms1588 KiB
4Accepted2ms1588 KiB
5Accepted2ms1588 KiB
6Accepted2ms1588 KiB
7Accepted2ms1588 KiB
subtask310/10
8Accepted2ms1588 KiB
9Accepted2ms1588 KiB
10Accepted2ms1588 KiB
11Accepted2ms1588 KiB
12Accepted3ms2136 KiB
subtask40/10
13Accepted4ms2100 KiB
14Accepted2ms1588 KiB
15Accepted3ms1600 KiB
16Accepted3ms1588 KiB
17Accepted104ms26260 KiB
18Wrong answer28ms6148 KiB
19Wrong answer39ms8040 KiB
20Wrong answer28ms6212 KiB
subtask50/10
21Accepted6ms2356 KiB
22Accepted2ms1780 KiB
23Accepted3ms1588 KiB
24Accepted3ms1588 KiB
25Accepted41ms16208 KiB
26Wrong answer4ms2376 KiB
27Wrong answer6ms2376 KiB
subtask60/60
28Accepted2ms1588 KiB
29Accepted2ms1784 KiB
30Accepted2ms1588 KiB
31Accepted3ms1844 KiB
32Accepted3ms1844 KiB
33Accepted4ms1844 KiB
34Accepted6ms2456 KiB
35Accepted6ms2488 KiB
36Accepted6ms2400 KiB
37Accepted94ms26288 KiB
38Wrong answer32ms6112 KiB
39Wrong answer32ms6224 KiB
40Wrong answer28ms6196 KiB
41Wrong answer30ms6172 KiB
42Wrong answer30ms6196 KiB
43Wrong answer29ms6196 KiB
44Wrong answer28ms6180 KiB
45Wrong answer46ms7988 KiB
46Wrong answer32ms6304 KiB
47Wrong answer28ms6224 KiB
48Wrong answer28ms6188 KiB
49Wrong answer28ms6264 KiB
50Wrong answer28ms6192 KiB