Submission #1004510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004510		0pt1mus23	Railway (BOI17_railway)	C++14	0 / 100	1042 ms	35264 KiB

railway

#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 toxun[sze];
int vis[sze];

void mal(){
    int m,k;
    vector<pair<int,int>> tracks;
    cin>>n>>m>>k;
    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});
    }
    build(1);
    /*

        depthi en boyuk olan LCA ,
        o LCA in altindaki en balaca depthli 
    */
    int mx = -1;
    int at = 0;
    vector<int> lst;
    for(int i=0;i<m;i++){
        int s;
        cin>>s;
        
        int a,b;
        cin>>a>>b;
        lst.pb(a);
        lst.pb(b);
        // cout<<a<<" "<<b<<endl;
        int x = ata(a,b);
        // cout<<x<<endl;
        if(depth[x]>mx){
            mx=depth[x];
            at=x;
        }
    }
    up[1][0]=-1;
    for(auto v:lst){
        int x = v;
        while(x!=-1 && !vis[x] && depth[x]>=mx){
            toxun[x]++;
            x = up[x][0];
        }
    }
    set<pair<int,int>> var;
    for(auto v:lst){
        // cout<<v<<" : "<<toxun[v]<<endl;
        if(toxun[v]>=k){
            if(v!=1){
                int a = min(v,up[v][0]);
                int b = max(v,up[v][0]);
                var.ins({a,b});
            }
        }
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
        int a = tracks[i].first;
        int b = tracks[i].second;
        if(var.count({min(a,b),max(a,b)})){
            ans.pb(i+1);
        }
    }
    cout<<ans.size()<<endl;
    for(auto v:ans){
        cout<<v<<" ";
    }
    cout<<endl;


}   

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

Compilation message (stderr)

railway.cpp: In function 'void mal()':
railway.cpp:88:9: warning: variable 'at' set but not used [-Wunused-but-set-variable]
   88 |     int at = 0;
      |         ^~

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