Submission #1004992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004992		0pt1mus23	Railway (BOI17_railway)	C++14	100 / 100	88 ms	43648 KiB

railway

/*
    Reshad sensei tutorial
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5+10, inf = 2e18, prime = 23;

vector<int> graph[sze];
int timer;
int L;
int n;
vector<vector<int>> up;

vector<int> giris,cixis;
int depth[sze];
void dfs(int node,int p){
    giris[node]=timer++;
    if(p!=node){
        depth[node]=depth[p]+1;
    }
    up[node][0]=p;
    for(int i=1;i<=L;i++){
        up[node][i]=up[up[node][i-1]][i-1];
    }

    for(auto v:graph[node]){
        if(v!=p){
            dfs(v,node);
        }
    }
    cixis[node]=timer++;
}

bool checkata(int a,int b){// A,  B'nin ATASIMI ?
    return (giris[a]<=giris[b] && cixis[a]>=cixis[b]);
}

int ata(int u,int v){
    if(checkata(u,v)){
        return u;
    }
    if(checkata(v,u)){
        return v;
    }
    for(int i=L;i>=0;i--){
        if(!checkata(up[u][i],v)){
            u=up[u][i];
        }
    }
    return up[u][0];
}

void build(int root){
    giris.resize(n+1);
    cixis.resize(n+1);
    timer=0;
    L = ceil(log2(n));
    up.assign(n+1,vector<int>(L+1));
    dfs(root,root);
}

int sub[sze];

int deg[sze];

void dfs2(int node,int p=-1){
    
    for(auto v:graph[node]){
        if(v!=p){
            dfs2(v,node);
            sub[node]+=sub[v];
        }
    }
}



void mal(){
    int m,k;
    vector<pair<int,int>> tracks;
    cin>>n>>m>>k;
    int root = 1;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
        tracks.pb({u,v});
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==1){
            root=i;
            break;
        }
    }
    build(root);
    
    
    vector<int> lst;
    
    int x;
    for(int p=0;p<m;p++){
        int s;
        cin>>s;
        lst.clear();
        for(int j=0;j<s;j++){
            cin>>x;
            lst.pb(x);
        }
        sort(all(lst),[&](int a,int b){
            return giris[a]<giris[b];
        });
        lst.pb(lst[0]);
        for(int i=0;i<s;i++){
            int a = lst[i];
            int b = lst[i+1];
            int c = ata(a,b);
            sub[a]++;
            sub[b]++;
            sub[c]-=2;
        }

        
    }
    
    dfs2(root);

    // for(int i=1;i<=n;i++){
    //     cout<<i<<" "<<sub[i]<<endl;
    // }
    set<pair<int,int>> var;
    
    for(int i=1;i<=n;i++){
        if(sub[i]>=2*k){
            var.insert({min(i,up[i][0]),max(i,up[i][0])});
        }   
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
        int a = tracks[i].first,b = tracks[i].second;
        if(var.count({min(a,b),max(a,b)})){
            ans.pb(i);
        }
    }

    cout<<ans.size()<<endl;
    for(auto v:ans){
        cout<<v+1<<" ";
    }
    cout<<endl;

}   

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25