| 16185 | 2025-04-13 17:56:22 | lacito | Turista járatok | cpp17 | Wrong answer 20/100 | 104ms | 26288 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;
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 2ms | 1616 KiB | ||||
| 2 | Accepted | 6ms | 2368 KiB | ||||
| subtask2 | 10/10 | ||||||
| 3 | Accepted | 2ms | 1588 KiB | ||||
| 4 | Accepted | 2ms | 1588 KiB | ||||
| 5 | Accepted | 2ms | 1588 KiB | ||||
| 6 | Accepted | 2ms | 1588 KiB | ||||
| 7 | Accepted | 2ms | 1588 KiB | ||||
| subtask3 | 10/10 | ||||||
| 8 | Accepted | 2ms | 1588 KiB | ||||
| 9 | Accepted | 2ms | 1588 KiB | ||||
| 10 | Accepted | 2ms | 1588 KiB | ||||
| 11 | Accepted | 2ms | 1588 KiB | ||||
| 12 | Accepted | 3ms | 2136 KiB | ||||
| subtask4 | 0/10 | ||||||
| 13 | Accepted | 4ms | 2100 KiB | ||||
| 14 | Accepted | 2ms | 1588 KiB | ||||
| 15 | Accepted | 3ms | 1600 KiB | ||||
| 16 | Accepted | 3ms | 1588 KiB | ||||
| 17 | Accepted | 104ms | 26260 KiB | ||||
| 18 | Wrong answer | 28ms | 6148 KiB | ||||
| 19 | Wrong answer | 39ms | 8040 KiB | ||||
| 20 | Wrong answer | 28ms | 6212 KiB | ||||
| subtask5 | 0/10 | ||||||
| 21 | Accepted | 6ms | 2356 KiB | ||||
| 22 | Accepted | 2ms | 1780 KiB | ||||
| 23 | Accepted | 3ms | 1588 KiB | ||||
| 24 | Accepted | 3ms | 1588 KiB | ||||
| 25 | Accepted | 41ms | 16208 KiB | ||||
| 26 | Wrong answer | 4ms | 2376 KiB | ||||
| 27 | Wrong answer | 6ms | 2376 KiB | ||||
| subtask6 | 0/60 | ||||||
| 28 | Accepted | 2ms | 1588 KiB | ||||
| 29 | Accepted | 2ms | 1784 KiB | ||||
| 30 | Accepted | 2ms | 1588 KiB | ||||
| 31 | Accepted | 3ms | 1844 KiB | ||||
| 32 | Accepted | 3ms | 1844 KiB | ||||
| 33 | Accepted | 4ms | 1844 KiB | ||||
| 34 | Accepted | 6ms | 2456 KiB | ||||
| 35 | Accepted | 6ms | 2488 KiB | ||||
| 36 | Accepted | 6ms | 2400 KiB | ||||
| 37 | Accepted | 94ms | 26288 KiB | ||||
| 38 | Wrong answer | 32ms | 6112 KiB | ||||
| 39 | Wrong answer | 32ms | 6224 KiB | ||||
| 40 | Wrong answer | 28ms | 6196 KiB | ||||
| 41 | Wrong answer | 30ms | 6172 KiB | ||||
| 42 | Wrong answer | 30ms | 6196 KiB | ||||
| 43 | Wrong answer | 29ms | 6196 KiB | ||||
| 44 | Wrong answer | 28ms | 6180 KiB | ||||
| 45 | Wrong answer | 46ms | 7988 KiB | ||||
| 46 | Wrong answer | 32ms | 6304 KiB | ||||
| 47 | Wrong answer | 28ms | 6224 KiB | ||||
| 48 | Wrong answer | 28ms | 6188 KiB | ||||
| 49 | Wrong answer | 28ms | 6264 KiB | ||||
| 50 | Wrong answer | 28ms | 6192 KiB | ||||