Submission #1173393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173393		duonggsimp	Railway (BOI17_railway)	C++20	100 / 100	129 ms	48836 KiB

railway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define MOD 1000000000
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

ll n,m,k;
ll cnt;
ll c[100005];
ll h[100005];
ll f[100005];
ll tin[100005];
ll par[100005][20];
vector <ll> a[100005];
vector <ll> res;
map <ii,ll> mp;

void dfs(ll x,ll p){

  tin[x] = ++cnt;
  for (ll i : a[x]){
    if (i == p) continue;
    h[i] = h[x] + 1;
    par[i][0] = x;
    dfs(i,x);
  }
}

void setup(){
  for (long j=1; j<=18; j++){
    for (long i=1; i<=n; i++){
      par[i][j] = par[par[i][j-1]][j-1];
    }
  }
}

ll lca(ll u,ll v){

  if (h[u] < h[v]) swap(u,v);
  for (long i=18; i>=0; i--){
    if (h[par[u][i]] >= h[v]) u = par[u][i];
  }

  if (u == v) return u;
  for (long i=18; i>=0; i--){
    if (par[u][i] != par[v][i]){
      u = par[u][i];
      v = par[v][i];
    }
  }
  return par[u][0];
}

void dfs2(ll x,ll p){

  for (ll i : a[x]){
    if (i == p) continue;
    dfs2(i,x);
    f[x] += f[i];
  } if (f[x] >= 2*k) res.pb(mp[{x,par[x][0]}]);

}

bool cmp(ll a,ll b){
  return tin[a] < tin[b];
}

signed main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  cin >> n >> m >> k;

  for (long i=1; i<n; i++){
    ll u,v; cin >> u >> v;
    a[u].pb(v);
    a[v].pb(u);
    mp[{u,v}] = mp[{v,u}] = i;
  }

  h[1] = 1;
  dfs(1,0);
  setup();

  while (m--){
    ll t; cin >> t;
    for (long i=1; i<=t; i++) cin >> c[i];
    sort(c+1,c+t+1,cmp);

    c[t+1] = c[1];
    for (long i=2; i<=t+1; i++){
      f[c[i-1]]++;
      f[c[i]]++;
      f[lca(c[i-1],c[i])] -= 2;
    }
  }

  dfs2(1,1);

  cout << res.size() << endl;
  sort(res.begin(),res.end());
  for (ll it : res) cout << it << ' ';



}

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