Submission #1156907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156907		tungkhoa08	Railway (BOI17_railway)	C++17	0 / 100	1096 ms	24904 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define i2 pair<int,int>
int kq,ttt[200005],kt[200004],dp[100005][23],h[200005],n,m,k,dem[200004];
vector <i2>g[200005];
vector <int>luu;
void dfs(int u,int pa){
    //cout<<u<<' ';
    for (i2 i:g[u]){
        int v=i.first;
        int tt=i.second;
        if (v!=pa){
            h[v]=h[u]+1;
            dp[v][0]=u;
            ttt[v]=tt;
            dfs(v,u);
        }
    }
}
void ktao(){
    for (int i=1;i<=20;i++){
        for (int u=1;u<=n;u++) dp[u][i]=dp[dp[u][i-1]][i-1];
    }
}
int lca(int u,int v){
    if (h[u]<h[v]) swap(u,v);
    if (h[u]!=h[v]){
        int k=h[u]-h[v];
        for (int i=20;i>=0;i--){
            int ok=(k>>i)&1;
            if (ok==1) u=dp[u][i];
        }
    }
    if (u==v) return u;
    int k=log2(h[u]);
    for (int i=k;i>=0;i--){
        int u1=dp[u][i];
        int v1=dp[v][i];
        if (u1!=v1){
            u=dp[u][i];
            v=dp[v][i];
        }
    }
    return dp[u][0];
}
void dfs1(int u,int chung){
   if (u==chung) return;
   kt[ttt[u]]=1;
   dfs1(dp[u][0],chung);
}
void work(){
    for (int i:luu){
        for (int j:luu) if (i!=j){
            int chung=lca(i,j);
            dfs1(i,chung);
            dfs1(j,chung);
        }
    }
    //dfs1(5,1);
    for (int i=1;i<=n-1;i++) if (kt[i]==1) dem[i]++;
    for (int i=1;i<=n-1;i++) kt[i]=0;;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("suaduong.inp","r",stdin);
//    freopen("suaduong.out","w",stdout);
    cin>>n>>m>>k;
    for (int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    dfs(1,0);
    ktao();
    for (int i=1;i<=m;i++){
        int x;
        cin>>x;
        for (int j=1;j<=x;j++){
            int u;
            cin>>u;
            luu.push_back(u);
        }
        work();
        luu.clear();
    }
    for (int i=1;i<=n-1;i++) if (dem[i]>=k) kq++;
    cout<<kq<<'\n';
    for (int i=1;i<=n-1;i++) if (dem[i]>=k) cout<<i<<' ';
    return 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