5267 | 2023-04-24 21:41:40 | k_balint | Turista járatok | cpp14 | Wrong answer 10/100 | 136ms | 51764 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=40005;
int n,m,k,tt;
int id;
vector<pair<int,int>> adj[c];
int t[c],l[c],vag[c],comp[10*c];
bool volt[10*c];
bool dp[c];
pair<int,int> el[10*c];
stack<int> st;
vector<int> tree[c];
void dfs(int v, int p){
++tt;
t[v]=l[v]=tt;
int db=0;
for(pair<int,int> x:adj[v]){
if(x.first==p) continue;
if(!volt[x.second]) {st.push(x.second); volt[x.second]=1;}
if(!t[x.first]){
++db;
dfs(x.first,v);
l[v]=min(l[v],l[x.first]);
if(p!=0 && l[x.first]>=t[v]){
if(vag[v]==0){++id; vag[v]=id;}
++id;
while(st.top()!=x.second){
int cur=st.top(); st.pop();
comp[cur]=id;
}
comp[st.top()]=id;
st.pop();
}
else if(p==0){
if(db==2){++id; vag[v]=id;}
++id;
while(!st.empty()){
int cur=st.top(); st.pop();
comp[cur]=id;
}
}
}
else l[v]=min(l[v],t[x.first]);
}
}
bool vis[c];
void dfs2(int v, int p){
if(dp[p]) dp[v]=1;
vis[v]=1;
for(int x:tree[v]){
if(!vis[x]) dfs2(x,v);
}
}
bool ans[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;
el[i]=make_pair(a,b);
adj[a].push_back(make_pair(b,i));
adj[b].push_back(make_pair(a,i));
}
tt=0,id=0;
dfs(1,0);
int z=0;
for(int i=1;i<=m;i++){
int a=el[i].first,b=el[i].second;
int cm=comp[i];
if(a==1 || b==1) z=cm;
if(i<=k) dp[cm]=1;
if(vag[a]!=0){
tree[vag[a]].push_back(cm);
tree[cm].push_back(vag[b]);
}
if(vag[b]!=0){
tree[vag[b]].push_back(cm);
tree[cm].push_back(vag[b]);
}
}
if(vag[1]!=0) dfs2(vag[1],0);
else dfs2(z,0);
ans[1]=0;
for(int i=2;i<=m;i++){
if(dp[comp[i]]) {
if(vag[el[i].first]==0) ans[el[i].first]=1;
if(vag[el[i].second]==0) ans[el[i].second]=1;
}
}
int cnt=0;
for(int i=2;i<=n;i++){
if(vag[i]!=0 && dp[vag[i]]) ans[i]=1;
if(ans[i]) ++cnt;
}
cout << cnt << endl;
for(int i=1;i<=m;i++){
if(ans[i]) cout<<i << ' ';
}
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 4ms | 5668 KiB | ||||
2 | Accepted | 10ms | 7824 KiB | ||||
subtask2 | 0/10 | ||||||
3 | Wrong answer | 4ms | 6068 KiB | ||||
4 | Wrong answer | 4ms | 6284 KiB | ||||
5 | Accepted | 4ms | 6492 KiB | ||||
6 | Accepted | 4ms | 6708 KiB | ||||
7 | Wrong answer | 4ms | 7056 KiB | ||||
subtask3 | 0/10 | ||||||
8 | Accepted | 4ms | 7268 KiB | ||||
9 | Wrong answer | 4ms | 7468 KiB | ||||
10 | Wrong answer | 4ms | 7432 KiB | ||||
11 | Wrong answer | 4ms | 7876 KiB | ||||
12 | Wrong answer | 7ms | 8788 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Wrong answer | 8ms | 9996 KiB | ||||
14 | Accepted | 4ms | 7908 KiB | ||||
15 | Accepted | 4ms | 8304 KiB | ||||
16 | Accepted | 4ms | 8472 KiB | ||||
17 | Accepted | 127ms | 51160 KiB | ||||
18 | Accepted | 41ms | 16740 KiB | ||||
19 | Wrong answer | 59ms | 20036 KiB | ||||
20 | Wrong answer | 43ms | 16984 KiB | ||||
subtask5 | 10/10 | ||||||
21 | Accepted | 9ms | 10096 KiB | ||||
22 | Accepted | 4ms | 8336 KiB | ||||
23 | Accepted | 4ms | 8648 KiB | ||||
24 | Accepted | 4ms | 8532 KiB | ||||
25 | Accepted | 82ms | 33468 KiB | ||||
26 | Accepted | 9ms | 9980 KiB | ||||
27 | Accepted | 9ms | 9928 KiB | ||||
subtask6 | 0/60 | ||||||
28 | Accepted | 4ms | 8500 KiB | ||||
29 | Accepted | 4ms | 8780 KiB | ||||
30 | Accepted | 6ms | 9204 KiB | ||||
31 | Accepted | 6ms | 9332 KiB | ||||
32 | Accepted | 7ms | 9604 KiB | ||||
33 | Accepted | 7ms | 9760 KiB | ||||
34 | Accepted | 10ms | 10728 KiB | ||||
35 | Accepted | 10ms | 10720 KiB | ||||
36 | Accepted | 9ms | 10608 KiB | ||||
37 | Accepted | 136ms | 51764 KiB | ||||
38 | Accepted | 43ms | 17300 KiB | ||||
39 | Accepted | 43ms | 17316 KiB | ||||
40 | Accepted | 41ms | 17272 KiB | ||||
41 | Wrong answer | 41ms | 17316 KiB | ||||
42 | Wrong answer | 41ms | 17332 KiB | ||||
43 | Accepted | 43ms | 17276 KiB | ||||
44 | Wrong answer | 41ms | 17404 KiB | ||||
45 | Accepted | 56ms | 20532 KiB | ||||
46 | Wrong answer | 41ms | 17324 KiB | ||||
47 | Wrong answer | 41ms | 17336 KiB | ||||
48 | Accepted | 41ms | 17200 KiB | ||||
49 | Accepted | 41ms | 17396 KiB | ||||
50 | Accepted | 43ms | 17332 KiB |