161852025-04-13 17:56:22lacitoTurista járatokcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1616 KiB
2Elfogadva6ms2368 KiB
subtask210/10
3Elfogadva2ms1588 KiB
4Elfogadva2ms1588 KiB
5Elfogadva2ms1588 KiB
6Elfogadva2ms1588 KiB
7Elfogadva2ms1588 KiB
subtask310/10
8Elfogadva2ms1588 KiB
9Elfogadva2ms1588 KiB
10Elfogadva2ms1588 KiB
11Elfogadva2ms1588 KiB
12Elfogadva3ms2136 KiB
subtask40/10
13Elfogadva4ms2100 KiB
14Elfogadva2ms1588 KiB
15Elfogadva3ms1600 KiB
16Elfogadva3ms1588 KiB
17Elfogadva104ms26260 KiB
18Hibás válasz28ms6148 KiB
19Hibás válasz39ms8040 KiB
20Hibás válasz28ms6212 KiB
subtask50/10
21Elfogadva6ms2356 KiB
22Elfogadva2ms1780 KiB
23Elfogadva3ms1588 KiB
24Elfogadva3ms1588 KiB
25Elfogadva41ms16208 KiB
26Hibás válasz4ms2376 KiB
27Hibás válasz6ms2376 KiB
subtask60/60
28Elfogadva2ms1588 KiB
29Elfogadva2ms1784 KiB
30Elfogadva2ms1588 KiB
31Elfogadva3ms1844 KiB
32Elfogadva3ms1844 KiB
33Elfogadva4ms1844 KiB
34Elfogadva6ms2456 KiB
35Elfogadva6ms2488 KiB
36Elfogadva6ms2400 KiB
37Elfogadva94ms26288 KiB
38Hibás válasz32ms6112 KiB
39Hibás válasz32ms6224 KiB
40Hibás válasz28ms6196 KiB
41Hibás válasz30ms6172 KiB
42Hibás válasz30ms6196 KiB
43Hibás válasz29ms6196 KiB
44Hibás válasz28ms6180 KiB
45Hibás válasz46ms7988 KiB
46Hibás válasz32ms6304 KiB
47Hibás válasz28ms6224 KiB
48Hibás válasz28ms6188 KiB
49Hibás válasz28ms6264 KiB
50Hibás válasz28ms6192 KiB