Submission #1092786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092786		juicy	Railway (BOI17_railway)	C++17	100 / 100	77 ms	25096 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], par[N], cnt[N], sz[N], ind[N];
bool spec[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;
      ++cnt[x];
      spec[x] = 1;
    }
    sort(cnd.begin(), cnd.end(), cmp);
    for (int i = 1; i < s; ++i) {
      cnd.push_back(lca(cnd[i], cnd[i - 1]));
    }
    sort(cnd.begin(), cnd.end(), cmp);
    cnd.erase(unique(cnd.begin(), cnd.end()), cnd.end());
    vector<int> st;
    for (int u : cnd) {
      while (st.size() && R[st.back()] < L[u]) {
        st.pop_back();
      }
      par[u] = st.size() ? st.back() : 0;
      sz[u] = 0;
      st.push_back(u);
    }
    for (int i = cnd.size() - 1; ~i; --i) {
      int u = cnd[i];
      sz[u] += spec[u];
      if (!par[u]) {
        cnt[u] -= sz[u];
      } else {
        cnt[u] -= sz[u] - 1;
        ++sz[par[u]];
      }
    }
    for (int u : cnd) {
      spec[u] = 0;
    }
  }
  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] >= 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