Submission #1282403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282403		hanguyendanghuy	Railway (BOI17_railway)	C++20	100 / 100	76 ms	22980 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define fi first
#define se second
const ll MAXN=1e5+5,INF=1e9,MOD=1e9+7;
ll n,m,i,j,k,p,dem,f,ans,needcnt,luu[MAXN],pref[MAXN],en[MAXN],cnt[MAXN],par[MAXN],dist[MAXN],chain[MAXN],headchain[MAXN],pos[MAXN],cntchain=1,de[MAXN],sz[MAXN];
vector<ll> adj[MAXN];
pair<ll,ll> mark[MAXN];
vector<pair<ll,ll>> sweep[MAXN],edge[MAXN];
deque<ll> dq;
void dfs(ll st){
    sz[st]=1;
    for(auto x:adj[st]){
        if(de[x]) continue;
        de[x]=de[st]+1;
        par[x]=st;
        dfs(x);
        sz[st]+=sz[x];
    }
}
void HLD(ll u){
    if(!headchain[cntchain])
        headchain[cntchain]=u;
    chain[u]=cntchain;
    pos[u]=++dem;
    en[cntchain]=dem;
    ll v=-1;
    for(auto x:adj[u])
        if(!chain[x]&&(u==-1||sz[x]>sz[v])) v=x;
    if(v>0) HLD(v);
    for(auto x:adj[u]){
        if(!chain[x]){
            cntchain++;
            HLD(x);
        }
    } 
}
void lca(ll u,ll v){
  while(chain[u]!=chain[v]){
      if(chain[u]<chain[v]) swap(u,v);
	  if(!luu[chain[u]]){
	  	dq.pb(chain[u]);
	  	luu[chain[u]]=1;
	  }
      mark[chain[u]].fi=min(mark[chain[u]].fi,pos[headchain[chain[u]]]);
      mark[chain[u]].se=max(mark[chain[u]].se,pos[u]);
      u=par[headchain[chain[u]]];
  }
  if(de[u]>de[v]) swap(u,v);
  if(!luu[chain[u]]){
  	dq.pb(chain[u]);
  	luu[chain[u]]=1;
  }
    mark[chain[u]].fi=min(mark[chain[u]].fi,pos[u]+1);
    mark[chain[u]].se=max(mark[chain[u]].se,pos[v]);
}
void solve(ll u,ll pre,ll countedge,ll id){
	countedge+=pref[pos[u]];
  cnt[id]=countedge;
  for(auto x:edge[u]){
    if(x.fi==pre) continue;
    if(chain[x.fi]!=chain[u]) solve(x.fi,u,0,x.se);
    else solve(x.fi,u,countedge,x.se);
  } 
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  cin>>n>>m>>needcnt;
  for(i=1;i<n;i++){
      ll u,v;
      cin>>u>>v;
      adj[u].pb(v);
      adj[v].pb(u);
      edge[u].pb({v,i});
      edge[v].pb({u,i});
  }
  de[1]=1;
  dfs(1);
  HLD(1);
  for(i=1;i<=cntchain;i++)
    mark[i]={INF,0};
  for(i=1;i<=m;i++){
    cin>>k;
    ll u;
    cin>>u;
    for(j=2;j<=k;j++){
      ll v;
      cin>>v;
      lca(u,v);
    }
    while(dq.size()){
    	f=dq.front();
    	dq.pop_front();
      	pref[mark[f].fi]++;
      	if(mark[f].se<en[f])
      		pref[mark[f].se+1]--;
        mark[f]={INF,0};
        luu[f]=0;
    }
  }
  solve(1,1,0,0);
  vector<ll> b;
  for(i=1;i<n;i++){
    if(cnt[i]>=needcnt)
      b.pb(i);
  }
  cout<<b.size()<<'\n';
  for(ll x:b) cout<<x<<" ";
}

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