Submission #1092788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092788		juicy	Railway (BOI17_railway)	C++17	100 / 100	76 ms	24268 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17;

int n, m, k;
int L[N], R[N], pr[LG][N], dep[N], cnt[N], ind[N];
vector<array<int, 2>> g[N];

int timer;

void dfs(int u) {
  L[u] = ++timer;
  for (auto [v, id] : g[u]) {
    if (!L[v]) {
      ind[v] = id;
      dep[v] = dep[u] + 1;
      pr[0][v] = u;
      for (int i = 1; i < LG; ++i) {
        pr[i][v] = pr[i - 1][pr[i - 1][v]];
      }
      dfs(v);
    }
  } 
  R[u] = timer;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int i = LG - 1; ~i; --i) {
    if (dep[u] - (1 << i) >= dep[v]) {
      u = pr[i][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = LG - 1; ~i; --i) {
    if (pr[i][u] ^ pr[i][v]) {
      u = pr[i][u];
      v = pr[i][v];
    }
  }
  return pr[0][u];
}

bool cmp(int u, int v) {
  return L[u] < L[v];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  dfs(1);
  while (m--) {
    int s; cin >> s;
    vector<int> cnd(s);
    for (int &x : cnd) {
      cin >> x;
    }
    sort(cnd.begin(), cnd.end(), cmp);
    for (int i = 0; i < s; ++i) {
      int u = cnd[i], v = cnd[(i + 1) % s];
      ++cnt[u], ++cnt[v], cnt[lca(u, v)] -= 2;
    }
  }
  vector<int> ord(n); iota(ord.begin(), ord.end(), 1);
  sort(ord.rbegin(), ord.rend(), cmp);
  vector<int> res;
  for (int u : ord) {
    if (cnt[u] >= 2 * k) {
      res.push_back(ind[u]);
    }
    cnt[pr[0][u]] += cnt[u];
  }
  cout << res.size() << "\n";
  sort(res.begin(), res.end());
  for (int x : res) {
    cout << x << " ";
  }
  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