Submission #1213365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213365		minhpk	Railway (BOI17_railway)	C++20	100 / 100	87 ms	83388 KiB

railway

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,k;
vector <int> z[1000005];
int d[1000005];
int sta1[1000005];
int fin1[1000005];
int tour1;
int high[1000005];
vector <int> res;


int logarit[1000005];
int sta[1000005];
int fin[1000005];
int euler[1000005];
int tour;
pair<int,int> edge[1000005];
int val[1000005];
int st[300001][21];

vector <int> v;


void dfs(int i,int parent){
     tour++;
     sta[i]=tour;
     euler[tour]=i;

     tour1++;
     sta1[i]=tour1;

     for (auto p:z[i]){
         if (p==parent){
            continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
     }


    fin1[i]=tour1;

}

bool isanc(int x,int y){
    return sta1[x]>=sta1[y] && fin1[x]<=fin1[y];
}

bool cmp(int a,int b){
    return sta1[a]<sta1[b];
}

void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                  st[i][j]=l;
              }else{
                  st[i][j]=r;
              }
         }
    }
}

int lca(int x,int y){
    int l=min(sta[x],sta[y]);
    int r=max(sta[x],sta[y]);

    int j=logarit[r-l+1];
    int idx1=st[l][j];
    int idx2=st[r-(1<<j)+1][j];

    if (high[idx1]<high[idx2]){
        return idx1;
    }else{
        return idx2;
    }
}

void auxiliary(){
    sort(v.begin(),v.end(),cmp);

    int sz=v.size();
    for (int i=0;i<sz-1;i++){
         int pre= lca(v[i],v[i+1]);
         v.push_back(pre);
    }

    sort(v.begin(),v.end(),cmp);
    v.erase(unique(v.begin(),v.end()),v.end());
    int auxroot=v[0];
    stack<int> st;
    st.push(auxroot);

    for (int i=1;i<v.size();i++){
         int u=v[i];
         while (st.size() && !isanc(u,st.top())){
               st.pop();
         }
         int g=st.top();
         d[u]++;
         d[g]--;
       //  cout << u << " " << g << "\n";
         st.push(u);
    }
}

void dfs1(int i,int par){
    val[i]=d[i];
    for (auto p:z[i]){
         if (p==par){
            continue;
         }
         dfs1(p,i);
         val[i]+=val[p];
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> k;
    logarit[1]=0;
    for (int i=2;i<=1e6;i++){
         logarit[i]=logarit[i/2]+1;
    }
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
         edge[i]={x,y};
    }
    dfs(1,0);
    buildst();

    while (b--){
         int c;
         cin >> c;
         for (int i=1;i<=c;i++){
              int x;
              cin >> x;
              v.push_back(x);
         }
         auxiliary();
         v.clear();
    }
    dfs1(1,0);
    for (int i=1;i<a;i++){
         auto [x,y]=edge[i];
         if (high[x]<high[y]){
            swap(x,y);
         }
         if (val[x]>=k){
            // cout << val[x] << " " << x  << "\n";
             res.push_back(i);
         }
    }
    cout << res.size() << "\n";
    for (auto p:res){
         cout << p << " ";
    }
    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