Submission #1260664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260664		duonggsimp	Railway (BOI17_railway)	C++20	100 / 100	49 ms	24768 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
#define i3 pair<ii,ll>
#define fi first
#define se second
using namespace std;

int n,m,k;
vector<ii> a[100007];
int cnt, b[100007];
int id = 0;
int sta[100007], fin[100007];
int h[100007];
int par[100007][17];
ll pre[100007];
vector<int> res;

bool cmp(int a, int b) {
  return sta[a] < sta[b];
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u,v);

  int k = h[u] - h[v];
  for (int i=0; (1<<i)<=k; i++) {
    if ((k>>i)&1) u = par[u][i];
  }

  if (u == v) return u;

  for (int i=__lg(h[u]); i>=0; i--) {
    if (par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  }

  return par[u][0];
}

void dfs1(int i) {
  sta[i] = ++id;

  for (const ii &t : a[i]) {
    int j = t.first;

    if (j == par[i][0]) continue;

    h[j] = h[i] + 1;
    par[j][0] = i;

    for (int k=1; k<=16; k++) {
      par[j][k] = par[par[j][k-1]][k-1];
    }

    dfs1(j);
  }

  fin[i] = id;
}

void dfs2(int i) {
  for (const ii &j : a[i]) {
    if (j.fi == par[i][0]) continue;

    dfs2(j.fi);
    pre[i] += pre[j.fi];

    if (pre[j.fi] >= k) res.push_back(j.se);
  }

//  cerr << i << ' ' << pre[i] << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  #ifdef EMERGENCY_DEBUG
  freopen("TEMP.inp","r",stdin);
  freopen("TEMP.out","w",stdout);
  #endif

  cin >> n >> m >> k;

  for (int i=1; i<n; i++) {
    int u,v;
    cin >> u >> v;

    a[u].push_back({v,i});
    a[v].push_back({u,i});
  }

  dfs1(1);

  while (m--) {
    cin >> cnt;
    for (int i=1; i<=cnt; i++) {
      cin >> b[i];
    }

    sort(b+1,b+cnt+1,cmp);

    int u = lca(b[1],b[cnt]);

    pre[b[1]]++;
    pre[u]--;
    for (int i=2; i<=cnt; i++) {
      pre[b[i]]++;
      pre[u]--;

      int v = lca(b[i],b[i-1]);
      pre[v]--;
      pre[u]++;
    }
  }

  dfs2(1);

  cout << res.size() << '\n';
  sort(res.begin(),res.end());

  for (const int &i : res) cout << i << ' ';

  return 0;
}

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