Submission #850805

#	Time	Username	Problem	Language	Result	Execution time	Memory
850805		kderylo	Railway (BOI17_railway)	C++17	100 / 100	110 ms	30460 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int stala=1e5+10;
vector<int>w[stala];
vector<int>w2[stala];
vector<pair<int,int> >pom;
vector<int>result;
int nr[stala];
int postorder[stala];
int gl[stala];
int jump[stala][17];
int dp[stala];
int l=0;
void dfs(int k,int p)
{
    jump[k][0]=p;
    for(int i=0;i<(int)w[k].size();i++){
        if(w[k][i]!=p){
            gl[w[k][i]]=gl[k]+1;
            dfs(w[k][i],k);
        }
        nr[w[k][i]]=w2[k][i];
    }
    l++;
    postorder[k]=l;
}
void pre_lca(int ile)
{
    for(int i=1;i<=16;i++){
        for(int j=1;j<=ile;j++){
            jump[j][i]=jump[jump[j][i-1]][i-1];
        }
    }
}
int lca(int x,int y)
{
    if(gl[y]>gl[x]){
        swap(x,y);
    }
    for(int i=16;i>=0;i--){
        if(gl[jump[x][i]]>=gl[y]){
            x=jump[x][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=16;i>=0;i--){
        if(jump[x][i]!=jump[y][i]){
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}
void func()
{
    int all_lca=pom[0].second;
    dp[pom[0].second]++;
    for(int i=1;i<(int)pom.size();i++){
        all_lca=lca(all_lca,pom[i].second);
        dp[pom[i].second]++;
        int x=lca(pom[i-1].second,pom[i].second);
        dp[x]--;
    }
    dp[all_lca]--;
}
void final_dfs(int k,int p,int wsp)
{
    for(int i=0;i<(int)w[k].size();i++){
        if(w[k][i]!=p){
            final_dfs(w[k][i],k,wsp);
            dp[k]+=dp[w[k][i]];
        }
    }
    if(dp[k]>=wsp){
        result.push_back(nr[k]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,m,k;
    cin>>ile>>m>>k;
    for(int i=1;i<ile;i++){
        int a,b;
        cin>>a>>b;
        w[a].push_back(b);
        w[b].push_back(a);
        w2[a].push_back(i);
        w2[b].push_back(i);
    }
    gl[1]=1;
    dfs(1,1);
    pre_lca(ile);
    for(int i=1;i<=m;i++){
        pom.clear();
        int il;
        cin>>il;
        for(int j=1;j<=il;j++){
            int a;
            cin>>a;
            pom.push_back({postorder[a],a});
        }
        sort(pom.begin(),pom.end());
        func();
    }
    final_dfs(1,0,k);
    sort(result.begin(),result.end());
    cout<<(int)result.size()<<"\n";
    for(int i=0;i<(int)result.size();i++){
        cout<<result[i]<<" ";
    }

    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