Submission #1214391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214391		Warinchai	Railway (BOI17_railway)	C++20	100 / 100	176 ms	27324 KiB

railway

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[200005];
int lv[200005];
int pa[20][100005];
int sum[100005];
int in[100005];
int cur=0;
int n,m,k;
vector<int>ans;

void dfs(int u,int p){
    in[u]=++cur;
    pa[0][u]=p;
    lv[u]=lv[p]+1;
    for(int i=1;i<20;i++)pa[i][u]=pa[i-1][pa[i-1][u]];
    for(auto [x,id]:adj[u])if(x!=p){
        dfs(x,u);
    }
}

int lca(int a,int b){
    if(lv[a]<lv[b])swap(a,b);
    for(int i=19;i>=0;i--)if(lv[pa[i][a]]>=lv[b])a=pa[i][a];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(pa[i][a]!=pa[i][b])a=pa[i][a],b=pa[i][b];
    return pa[0][a];
}

void efs(int u,int p,int id){
    for(auto [x,id]:adj[u])if(x!=p){
        efs(x,u,id);
        sum[u]+=sum[x];
    }
    if(sum[u]>=k)ans.push_back(id);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    vector<pair<int,int>>edge;
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
        edge.push_back({a,b});
    }
    dfs(1,0);
    for(int i=0;i<m;i++){
        int s;cin>>s;
        vector<pair<int,int>>v;
        for(int j=0;j<s;j++){
            int x;cin>>x;
            v.push_back({in[x],x});
        }
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++){
            int x=v[i].second;
            int y=v[(i+1)%v.size()].second;
            int z=lca(x,y);
            sum[z]--;
            sum[x]++;
        }
    }
    efs(1,0,0);
    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for(auto x:ans)cout<<x+1<<" ";
}

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