Submission #1282390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282390		hanguyendanghuy	Railway (BOI17_railway)	C++20	0 / 100	1096 ms	589824 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,ans,needcnt,cnt[MAXN],par[MAXN],dist[MAXN],chain[MAXN],headchain[MAXN],pos[MAXN],cntchain=1,de[MAXN],sz[MAXN];
vector<ll> adj[MAXN],st[MAXN],en[MAXN];
pair<ll,ll> mark[MAXN];
vector<pair<ll,ll>> sweep[MAXN],edge[MAXN];
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;
    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);
        }
    } 
}
pair<ll,ll> merge(pair<ll,ll> a,pair<ll,ll> b){
  return {min(a.fi,b.fi),max(a.se,b.se)};
}
void lca(ll u,ll v){
  while(chain[u]!=chain[v]){
      if(chain[u]<chain[v]) swap(u,v);
      mark[chain[u]]=merge(mark[chain[u]],{pos[headchain[chain[u]]],pos[u]});
      u=par[headchain[chain[u]]];
  }
  if(de[u]>de[v]) swap(u,v);
  mark[chain[u]]=merge(mark[chain[u]],{pos[u]+1,pos[v]});
}
void solve(ll u,ll countedge,ll curst,ll curen,ll id){
  while(curst<st[chain[u]].size()&&st[chain[u]][curst]<=pos[u])
    countedge++,curst++;
  while(curen<en[chain[u]].size()&&en[chain[u]][curen]<pos[u])
    countedge--,curen++;
  cnt[id]=countedge;
  for(auto x:edge[u]){
    if(cnt[x.se]) continue;
    if(chain[x.fi]!=chain[u]) solve(x.fi,0,0,0,x.se);
    else solve(x.fi,countedge,curst,curen,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);
    } 
    for(ll j=1;j<=cntchain;j++)
      if(mark[j]!=make_pair(INF,0)){
        sweep[j].pb({mark[j]});
        mark[j]={INF,0};
      }
  }
  for(ll i=1;i<=cntchain;i++){
    for(auto x:sweep[i])
      st[i].pb(x.fi),en[i].pb(x.se);
    sort(st[i].begin(),st[i].end());
    sort(en[i].begin(),en[i].end());
  }
  solve(1,0,0,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: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25