Submission #1263723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263723		chinhhoang	Railway (BOI17_railway)	C++20	100 / 100	88 ms	36288 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int tin[N],tout[N],ST[N][20],sum[N],euler[N],h[N],LG[N+4],edge_par[N];
int cnt=0;
int n,m,k;
vector<pair<int,int>>adj[N];
void dfs(int u,int p){
    tin[u]=++cnt;
    euler[cnt]=u;
    for(auto it:adj[u]){
        int v=it.first;
        int i=it.second;
        if(v!=p){
            edge_par[v]=i;
            h[v]=h[u]+1;
            dfs(v,u);
            euler[++cnt]=u;
        }
    }
    tout[u]=cnt;
}
int combine(int i,int j){
    return (h[i]<h[j]?i:j);
}
bool cmp(int i,int j){
    return tin[i]<tin[j];
}
int LCA(int u,int v){
    u=tin[u];
    v=tin[v];
    if(u>v)swap(u,v);
    int k=LG[v-u+1];
    return combine(ST[u][k],ST[v-(1<<k)+1][k]);
}
void dfs_Ans(int u,int p){
    for(auto it:adj[u]){
        int v=it.first;
        int i=it.second;
        if(v==p)continue;
        dfs_Ans(v,u);
        sum[u]+=sum[v];
    }
}
int main(){
    //freopen("TREEDAY.INP","r",stdin);
   // freopen("REVENUE.OUT","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=2;i<=N;i++)LG[i]=LG[i/2]+1;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    dfs(1,1);
    for(int i=1;i<=cnt;i++)ST[i][0]=euler[i];
    for(int j=1;j<20;j++){
        for(int i=1;i+(1<<j)-1<=cnt;i++)ST[i][j]=combine(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
    }
    while(m--){
        int s;
        cin>>s;
        vector<int>nodes;
        for(int i=1;i<=s;i++){
            int v;
            cin>>v;
            nodes.push_back(v);
        }
        sort(nodes.begin(),nodes.end(),cmp);
        for(int i=1;i<s;i++)nodes.push_back(LCA(nodes[i-1],nodes[i]));
        sort(nodes.begin(),nodes.end(),cmp);
        nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
        stack<int>stk;
        stk.push(nodes[0]);
        for(int i=1;i<nodes.size();i++){
            while(stk.size()){
                int u=stk.top();
                if(tin[u]<=tin[nodes[i]]&&tout[nodes[i]]<=tout[u])break;
                stk.pop();
            }
            sum[stk.top()]--;
            sum[nodes[i]]++;
            stk.push(nodes[i]);
        }
    }
    dfs_Ans(1,1);
    vector<int>res;
    for(int i=1;i<=n;i++)if(sum[i]>=k)res.push_back(edge_par[i]);
    sort(res.begin(),res.end());
    cout<<res.size()<<'\n';
    for(auto v:res)cout<<v<<' ';
    cout<<'\n';
    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