Submission #1199411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199411		lucaskojima	Railway (BOI17_railway)	C++17	8 / 100	1096 ms	27240 KiB

railway

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int LOG = 20;

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, m, k; cin >> n >> m >> k;

  vector<vector<int>> adj(n + 1);
  vector<pii> edg;
  for (int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    edg.push_back({a, b});
  }

  vector<int> pai(n + 1), prof(n + 1);
  auto pre = [&](auto pre, int x) -> void {
    for (int k : adj[x]) {
      if (k == pai[x]) continue;
      pai[k] = x;
      prof[k] = prof[x] + 1;
      pre(pre, k);
    }
  }; pre(pre, 1);

  vector up(n + 1, vector<int>(LOG, -1));
  for (int i = 2; i <= n; i++)
    up[i][0] = pai[i];
  for (int k = 1; k < LOG; k++)
    for (int i = 1; i <= n; i++)
      if (up[i][k - 1] != -1)
        up[i][k] = up[up[i][k - 1]][k - 1];

  auto lift = [&](int x, int k) -> int {
    for (int i = 0; i < LOG; i++)
      if (x != -1) if ((k >> i) & 1)
        x = up[x][i];
    return x;
  };
  auto subtree = [&](int a, int b) -> bool { // b na subtree de a
    if (prof[b] < prof[a]) return false;
    b = lift(b, prof[b] - prof[a]);
    return a == b;
  };

  vector<vector<int>> hood(m);
  for (int i = 0; i < m; i++) {
    int s; cin >> s;
    hood[i].resize(s);
    for (auto &x : hood[i]) cin >> x;
  }

  vector<int> ans;
  for (int i = 0; i < n - 1; i++) {
    auto [a, b] = edg[i];
    int x = (prof[a] > prof[b] ? a : b);

    int cnt = 0;
    for (int j = 0; j < m; j++) {
      int sum = 0;
      for (int k : hood[j])
        if (subtree(x, k))
          sum++;
      if (sum != 0 && sum != sz(hood[j]))
        cnt++;
    }

    if (cnt >= k)
      ans.push_back(i + 1);
  }

  cout << sz(ans) << nl;
  for (int x : ans) cout << x << ' ';
  return 0;
}

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