제출 #1334002

#제출 시각아이디문제언어결과실행 시간메모리
1334002NewtonabcRailway (BOI17_railway)C++20
36 / 100
118 ms22096 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<pair<int,int>> adj[N];
int ti,p[N],d[N][18],dep[N],in[N],out[N],be[N],fw[N];
int query(int idx){int s=0; for(;idx;idx-=idx&-idx) s+=fw[idx]; return s;}
void upd(int idx,int v){for(;idx<N;idx+=idx&-idx) fw[idx]+=v;}
void dfs(int u,int p){
    d[u][0]=p;
    in[u]=++ti;
    for(auto [w,v]:adj[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        be[v]=w;
        dfs(v,u);
    } 
    out[u]=ti;
}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=17;i>=0;i--) if(dep[d[v][i]]>=dep[u]) v=d[v][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--) if(d[u][i]!=d[v][i]) u=d[u][i],v=d[v][i];
    return d[u][0];
}
int main(){
    int n,m,k; cin>>n >>m >>k;
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u >>v;
        adj[u].push_back({i+1,v});
        adj[v].push_back({i+1,u});
    }
    dep[1]=1;
    dfs(1,0);
    for(int j=1;j<=17;j++){
        for(int i=0;i<=n;i++){
            d[i][j]=d[d[i][j-1]][j-1];
        }
    }
    for(int i=0;i<m;i++){
        int x,o; cin>>x;
        vector<int> l;
        for(int j=0;j<x;j++){
            int s; cin>>s;
            l.push_back(s);
        }
        sort(l.begin(),l.end(),[&](int a,int b){
            return in[a]<in[b];
        });
        for(int j=0;j<x;j++){
            int nt=(j+1)%x;
            int lc=lca(l[j],l[nt]);
            upd(in[l[j]],1);
            upd(in[l[nt]],1);
            upd(in[lc],-2);
        }
    }
    vector<int> r;
    for(int i=2;i<=n;i++) if(query(out[i])-query(in[i]-1)>=2*k) r.push_back(be[i]);
    cout<<r.size() <<"\n";
    for(int i=0;i<r.size();i++){
        cout<<r[i] <<" \n"[i==(int)(r.size())-1];
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...