Submission #1165121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165121		fryingduc	Railway (BOI17_railway)	C++20	100 / 100	67 ms	22976 KiB

railway

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int LG = 17;
int n, m, k;
int eu[maxn], ev[maxn];
vector<int> g[maxn];
int tin[maxn], tout[maxn], timer;
int up[maxn][LG + 1], h[maxn];
int eid[maxn];
vector<int> cand;
int c[maxn];

void pre_dfs(int u, int prev) {
  tin[u] = ++timer;
  for (auto v:g[u]) {
    if (v == prev) continue;
    h[v] = h[u] + 1;
    up[v][0] = u;
    for (int i = 1; i <= LG; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    pre_dfs(v, u);
  }
  tout[u] = timer;
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG; i >= 0; --i) {
    if ((h[u] - h[v]) >> i & 1) u = up[u][i];
  }
  if (u == v) return u;
  for (int i = LG; i >= 0; --i) {
    if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
  }
  return up[v][0];
}

int dist(int u, int v) {
  return h[u] + h[v] - 2 * h[lca(u, v)];
}

void inc(int p, int u) {
  ++c[u], --c[p];
}

void upd(vector<int> &ver) {
  sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
    return tin[x] < tin[y];
  });
  for (int i = (int)ver.size() - 1; i > 0; --i) {
    ver.push_back(lca(ver[i], ver[i - 1]));
  }
  sort(ver.begin(), ver.end(), [](const int &x, const int &y) -> bool {
    return tin[x] < tin[y];
  });
  stack<int> st;
  st.push(ver[0]);
  auto is_anc = [&](int u, int v) {
    return tin[u] <= tin[v] and tout[v] <= tout[u];
  };
  for (int i = 1; i < (int)ver.size(); ++i) {
    while (!st.empty() and !is_anc(st.top(), ver[i])) st.pop();
    if (!st.empty()) {
      inc(st.top(), ver[i]);
    }
    st.push(ver[i]);
  }
}

void dfs(int u, int prev) {
  for (auto v:g[u]) {
    if (v == prev) continue;
    dfs(v, u);
    c[u] += c[v];
  }
  if (c[u] >= k and eid[u]) cand.push_back(eid[u]);
}

void solve() {
  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) { 
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    eu[i] = u, ev[i] = v;
  }
  pre_dfs(1, 0);
  for (int i = 1; i < n; ++i) {
    if (up[eu[i]][0] == ev[i]) swap(eu[i], ev[i]);
    eid[ev[i]] = i;
  }
  for (int i = 1; i <= m; ++i) { 
    int sz; cin >> sz;
    vector<int> ver(sz);
    for (auto &j : ver) {
      cin >> j;
    }
    upd(ver);
  }
  dfs(1, 0);
  sort(cand.begin(), cand.end());
  cout << (int)cand.size() << '\n';
  for (auto i : cand) {
    cout << i << " ";
  }
}

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

  solve();

  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