Submission #631115

#	Time	Username	Problem	Language	Result	Execution time	Memory
631115		anhduc2701	Railway (BOI17_railway)	C++17	100 / 100	189 ms	26868 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int pa[maxn][20];
vector<pair<int,int>>G[maxn];
int st[maxn];
int ou[maxn];
int eu[maxn];
int l=0;
int h[maxn];
int sub[maxn];
int idx[maxn];
int n,m,k;
bool cmp(int a,int b){
    return st[a]<st[b];
}
bool cmp1(int a,int b){
    return h[a]>h[b];
}
void dfs(int u,int p){
    st[u]=++l;
    eu[l]=u;
    for(auto v:G[u]){
        if(v.first==p)continue;
        pa[v.first][0]=u;
        h[v.first]=h[u]+1;
        dfs(v.first,u);
    }
    ou[u]=l;
}
void dfs_sub(int u,int p){
    for(auto [v,id]:G[u]){
        if(v!=p){
            idx[v]=id;
            dfs_sub(v,u);
            sub[u]+=sub[v];
        }
    }
}
void init(){
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            pa[i][j]=pa[pa[i][j-1]][j-1];
        }
    }
}
int lca(int a,int b){
    if(h[b]>h[a])swap(a,b);
    int d=h[a]-h[b];
    for(int k=0;k<20;k++){
        if(d&(1<<k))a=pa[a][k];
    }
    if(a==b)return a;
    for(int k=19;k>=0;k--){
        if(pa[a][k]!=pa[b][k]){
            a=pa[a][k];
            b=pa[b][k];
        }
    }
    return pa[a][0];
}
int main() {
    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,1);
    init();
    for(int i=0;i<m;i++){
        int s;
        cin>>s;
        vector<int>q;
        for(int i=0;i<s;i++){
            int x;cin>>x;
            q.push_back(x);
        }
        sort(q.begin(),q.end(),cmp);
        vector<int>lcas;
        for(int i=0;i<s-1;i++){
            lcas.push_back(lca(q[i],q[i+1]));
        }
        sort(lcas.begin(),lcas.end(),cmp1);
        lcas.erase(unique(lcas.begin(),lcas.end()),lcas.end());
        set<int>atual;
        for(int v:q){
            atual.insert(st[v]);
        }
        for(auto u:lcas){
            auto beg=atual.lower_bound(st[u]);
            auto ed=atual.upper_bound(ou[u]);
            vector<int>tmp;
            while(beg!=ed){
                ++sub[eu[*beg]];
                --sub[u];
                tmp.push_back(*beg);
                ++beg;
            }
            for(auto v:tmp){
                atual.erase(v);
            }
            atual.insert(st[u]);
        }
    }
    dfs_sub(1,1);
    vector<int>ans;
    for(int i=1;i<=n;i++){
        if(sub[i]>=k)ans.push_back(idx[i]);
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto v:ans){
        cout<<v<<' ';
    }
    cout<<'\n';
}

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