Submission #1156921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156921		tungkhoa08	Railway (BOI17_railway)	C++17	0 / 100	105 ms	47180 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>i2;
#define fi first
#define se second;
#define pb push_back;
int gu[100005],gv[100005],n,m,k,h[100005],dp[100005][30];
vector <int>kq,g[100005],luu[100005];
set <int> s[100005];
void dfs(int u,int pa){
    for (int v:g[u]){
        if (v!=pa){
            h[v]=h[u]+1;
            dp[v][0]=u;
            dfs(v,u);
        }
    }
}
void ktao(){
    for (int i=1;(1<<i)<=n;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) u=dp[u][i];
        }
    }
    if (u==v) return u;
    int k=__lg(h[u]);
    for (int i=k;i>=0;i--){
        int u1=dp[u][i];
        int v1=dp[v][i];
        if (v1!=u1){
            u=u1;
            v=v1;
        }
    }
    return dp[u][0];
}
int tinh(int u,int v){
    if (h[u]<h[v]) swap(u,v);
    return u;
}
void dfs2(int u,int pa){
    for (int v:g[u]){
        if (v!=pa){
            dfs2(v,u);
            if (s[v].size()>s[u].size()) swap(s[v],s[u]);
            for (int i :s[v]) s[u].insert(i);
        }
    }
    for (int i:luu[u]) if (s[u].size()!=0) s[u].erase(i);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("tree.inp","r",stdin);
//    freopen(" ","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);
        g[v].push_back(u);
        gu[i]=u;
        gv[i]=v;
    }
    h[1]=1;
    dfs(1,0);
    ktao();
    for (int i=1;i<=m;i++){
        int n1,t;
        cin>>n1;
        cin>>t;
        s[t].insert(i);
        for (int j=1;j<=n1-1;j++){
            int u;
            cin>>u;
            s[u].insert(i);
            t=lca(u,t);
        }
        luu[t].push_back(i);
    }
    dfs2(1,0);
    for (int i=1;i<=n-1;i++){
        if (s[tinh(gu[i],gv[i])].size()>=k) kq.push_back(i);
    }
    cout<<kq.size()<<'\n';
    for (int i:kq) 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