Submission #945780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945780	2024-03-14T07:39:12 Z	noyancanturk	Railway (BOI17_railway)	C++17	7 / 100	83 ms	18956 KB

railway

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1e5+100;
#else
    const int lim=1e5+3;
#endif

const int lglim=17;
    
#include "bits/stdc++.h"
using namespace std;
    
//#define int int64_t
#define pb push_back
    
const int mod=998244353;
//const int mod=(1ll<<61)-1;

using pii=pair<int,int>;

int n,m,k;
int tin[lim],tout[lim],dep[lim],tt=0;
int lift[lglim][lim];
vector<pii>v[lim];
int pare[lim];

inline void tour(int node,int par){
    tin[node]=tt++;
    dep[node]=dep[par]-1;
    lift[0][node]=par;
    int i=1;
    while(i<lglim&&(lift[i][node]=lift[i-1][lift[i-1][node]]))i++;
    for(auto [j,c]:v[node]){
        if(j^par){
            pare[j]=c;
            tour(j,node);
        }
    }
    tout[node]=tt-1;
}

int lgll[lim];

inline int lca(int x,int y){
    if(dep[y]<dep[x])swap(x,y);
    int dif=dep[y]-dep[x];
    while(dif){
        int lll=lgll[dif&-dif];
        dif-=1<<lll;
        x=lift[lll][x];
    }
    if(x==y)return x;
    for(int i=lgll[dep[x]];0<=i;i--){
        if(lift[i][x]^lift[i][y]){
            x=lift[i][x];
            y=lift[i][y];
        }
    }
    return lift[0][x];
}

int val[lim];
bool can[lim];
vector<int>ans;

inline int dfs(int node,int par){
    for(auto [j,c]:v[node]){
        if(j^par){
            val[node]+=dfs(j,node);
        }
    }
    if(2*k<=val[node]){
        can[pare[node]]=1;
    }
    return val[node];
}

inline void solve(){
    lgll[1]=0;
    for(int i=2;i<lim;i++){
        lgll[i]=lgll[i/2]+1;
    }
    cin>>n>>m>>k;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb({y,i});
        v[y].pb({x,i});
    }
    tour(1,0);
    int inds[n+1];
    for(int r=0;r<m;r++){
        int s;
        cin>>s;
        for(int i=0;i<s;i++){
            cin>>inds[i];
        }
        sort(inds,inds+s,[&](int i,int j) -> bool {
            return tin[i]<tin[j];
        });
        inds[s]=inds[0];
        for(int i=0;i<s;i++){
            val[inds[i]]++;
            val[inds[i+1]]++;
            val[lca(inds[i],inds[i+1])]-=2;
        }
    }
    dfs(1,0);
    int cnt=0;
    for(int i=0;i<n;i++){
        if(can[i])cnt++;
    }
    cout<<cnt<<"\n";
    for(int i=0;i<n;i++)if(can[i])cout<<i<<" ";
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else

#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Incorrect	4 ms	7000 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Incorrect	4 ms	7000 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	18780 KB	Output is correct
2	Correct	1 ms	6488 KB	Output is correct
3	Correct	83 ms	18496 KB	Output is correct
4	Correct	51 ms	18268 KB	Output is correct
5	Correct	43 ms	18816 KB	Output is correct
6	Correct	43 ms	18956 KB	Output is correct