Submission #945809

#	Time	Username	Problem	Language	Result	Execution time	Memory
945809		noyancanturk	Railway (BOI17_railway)	C++17	100 / 100	36 ms	20736 KiB

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>;

struct inpout{
    static const int sz=1<<15;
    char inp[sz];
    int curc=0,len=0;
    inline char gc(){
        if(curc==len){
            len=(int)fread(inp,1,sz,stdin);
            curc=0;
            if(!len)return -1;
        }
        return inp[curc++];
    }
    inline void readstr(char*c,int ll){
        for(int i=0;i<ll;i++){
            c[i]=gc();
        }
        gc();
    }
    inline int readuint(){
        int ans=0;
        char c=gc();
        while('0'<=c&&c<='9'){
            ans=10*ans+c-'0';
            c=gc();
        }
        return ans;
    }
    inline int readint(){
        char c=gc();
        bool isneg=(c=='-');
        int ans=0;
        if(!isneg)ans=c-'0';
        c=gc();
        while('0'<=c&&c<='9'){
            ans=10*ans+c-'0';
            c=gc();
        }
        if(isneg)return -ans;
        return ans;
    }
    char out[sz];
    int curind=0;
    inline void flush(){
        fwrite(out,1,curind,stdout);
        curind=0;
    }
    inline void putchar(char c){
        out[curind++]=c;
        if(curind==sz)flush();
    }
    char temp[10];
    inline void putint(int i){
        if(i<0){
            putchar('-');
            i=-i;
        }
        int lll=0;
        while(i){
            temp[lll++]=(i%10)+'0';
            i/=10;
        }
        while(lll){
            putchar(temp[--lll]);
        }
        putchar('\n');
    }
}io;

int n,m,k;
int tin[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;
    for(int i=1;i<lglim;i++){
        if(!(lift[i][node]=lift[i-1][lift[i-1][node]]))break;
    }
    for(auto [j,c]:v[node]){
        if(j^par){
            pare[j]=c;
            tour(j,node);
        }
    }
}

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;
    }
    n=io.readuint(),m=io.readuint(),k=io.readuint();
    for(int i=1;i<=n-1;i++){
        int x=io.readuint(),y=io.readuint();
        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;
        s=io.readuint();
        for(int i=0;i<s;i++){
            inds[i]=io.readuint();
        }
        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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25