5267 2023. 04. 24 21:41:40 k_balint Turista járatok cpp14 Hibás válasz 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 << ' ';
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 5668 KiB
2 Elfogadva 10ms 7824 KiB
subtask2 0/10
3 Hibás válasz 4ms 6068 KiB
4 Hibás válasz 4ms 6284 KiB
5 Elfogadva 4ms 6492 KiB
6 Elfogadva 4ms 6708 KiB
7 Hibás válasz 4ms 7056 KiB
subtask3 0/10
8 Elfogadva 4ms 7268 KiB
9 Hibás válasz 4ms 7468 KiB
10 Hibás válasz 4ms 7432 KiB
11 Hibás válasz 4ms 7876 KiB
12 Hibás válasz 7ms 8788 KiB
subtask4 0/10
13 Hibás válasz 8ms 9996 KiB
14 Elfogadva 4ms 7908 KiB
15 Elfogadva 4ms 8304 KiB
16 Elfogadva 4ms 8472 KiB
17 Elfogadva 127ms 51160 KiB
18 Elfogadva 41ms 16740 KiB
19 Hibás válasz 59ms 20036 KiB
20 Hibás válasz 43ms 16984 KiB
subtask5 10/10
21 Elfogadva 9ms 10096 KiB
22 Elfogadva 4ms 8336 KiB
23 Elfogadva 4ms 8648 KiB
24 Elfogadva 4ms 8532 KiB
25 Elfogadva 82ms 33468 KiB
26 Elfogadva 9ms 9980 KiB
27 Elfogadva 9ms 9928 KiB
subtask6 0/60
28 Elfogadva 4ms 8500 KiB
29 Elfogadva 4ms 8780 KiB
30 Elfogadva 6ms 9204 KiB
31 Elfogadva 6ms 9332 KiB
32 Elfogadva 7ms 9604 KiB
33 Elfogadva 7ms 9760 KiB
34 Elfogadva 10ms 10728 KiB
35 Elfogadva 10ms 10720 KiB
36 Elfogadva 9ms 10608 KiB
37 Elfogadva 136ms 51764 KiB
38 Elfogadva 43ms 17300 KiB
39 Elfogadva 43ms 17316 KiB
40 Elfogadva 41ms 17272 KiB
41 Hibás válasz 41ms 17316 KiB
42 Hibás válasz 41ms 17332 KiB
43 Elfogadva 43ms 17276 KiB
44 Hibás válasz 41ms 17404 KiB
45 Elfogadva 56ms 20532 KiB
46 Hibás válasz 41ms 17324 KiB
47 Hibás válasz 41ms 17336 KiB
48 Elfogadva 41ms 17200 KiB
49 Elfogadva 41ms 17396 KiB
50 Elfogadva 43ms 17332 KiB