Submission #1199422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199422		enzy	Railway (BOI17_railway)	C++20	100 / 100	108 ms	38592 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>v[maxn], resp;
int pre[maxn], pos[maxn], k, tmp, dp[maxn][20], pai[maxn], qtd[maxn], prof[maxn];
map<pair<int,int>,int>imp;
void dfs(int u){
    tmp++;
    pre[u]=tmp;
    for(int viz : v[u]){
        if(pre[viz]) continue;
        prof[viz]=prof[u]+1;
        pai[viz]=u;
        dfs(viz);
    }
    pos[u]=tmp;
}
int lca(int a, int b){
    if(prof[a]<prof[b]) swap(a,b);
    int d=prof[a]-prof[b];
    for(int k=0;k<20;k++) if(d&(1<<k)) a=dp[a][k];
    if(a==b) return a;
    for(int k=19;k>=0;k--){
        int na=dp[a][k], nb=dp[b][k];
        if(na!=nb){
            a=na; b=nb;
        }
    }
    return pai[a];
}
void calc(int u, int pai){
    for(int viz : v[u]){
        if(viz==pai) continue;
        calc(viz,u);
        qtd[u]+=qtd[viz];
    }
    if(qtd[u]>=k) resp.push_back(imp[{u,pai}]);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m; cin >> n >> m >> k;
    k*=2;
    for(int i=1;i<n;i++){
        int a, b; cin >> a >> b;
        imp[{a,b}]=imp[{b,a}]=i;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    pai[1]=1;
    for(int i=1;i<=n;i++) dp[i][0]=pai[i];
    for(int k=1;k<20;k++)
        for(int i=1;i<=n;i++) dp[i][k]=dp[dp[i][k-1]][k-1];
    for(int i=1;i<=m;i++){
        vector<pair<int,int>>aux;
        int x; cin >> x;
        for(int j=1;j<=x;j++){
            int a; cin >> a;
            aux.push_back({pre[a],a});
        }
        sort(aux.begin(),aux.end());
        int last=aux.back().second;
        for(auto p : aux){
            qtd[last]++; qtd[p.second]++;
            qtd[lca(last,p.second)]-=2;
            last=p.second;
        }
    }
    calc(1,1);
    sort(resp.begin(),resp.end());
    cout << resp.size() << endl;
    for(int a : resp) cout << a << " ";
    return 0;
} 

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