Submission #529996

#	Time	Username	Problem	Language	Result	Execution time	Memory
529996		Alex_tz307	Railway (BOI17_railway)	C++17	100 / 100	91 ms	25660 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int kLog = 16;
int timer, tin[1 + kN], tout[1 + kN], depth[1 + kN], edge[1 + kN], dp[1 + kN], lg2[1 + kN], anc[1 + kN][1 + kLog];
vector<pair<int, int>> g[1 + kN];

void precalc() {
  for (int i = 2; i < kN; ++i) {
    lg2[i] = lg2[i / 2] + 1;
  }
}

void dfs1(int u) {
  tin[u] = ++timer;
  for (int i = 1; i <= kLog; ++i) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
    if (anc[u][i] == 0) {
      break;
    }
  }
  for (auto it : g[u]) {
    int v, index;
    tie(v, index) = it;
    if (v != anc[u][0]) {
      anc[v][0] = u;
      depth[v] = depth[u] + 1;
      edge[v] = index;
      dfs1(v);
    }
  }
  tout[u] = timer;
}

void dfs2(int u) {
  for (auto it : g[u]) {
    int v = it.first;
    if (v != anc[u][0]) {
      dfs2(v);
      dp[u] += dp[v];
    }
  }
}

bool isAncestor(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int getLca(int u, int v) {
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  if (isAncestor(v, u)) {
    return v;
  }
  for (int i = lg2[depth[v]]; i >= 0; --i) {
    if (anc[v][i] && !isAncestor(anc[v][i], u)) {
      v = anc[v][i];
    }
  }
  return anc[v][0];
}

void testCase() {
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }
  dfs1(1);
  for (int i = 0; i < m; ++i) {
    int N;
    cin >> N;
    vector<int> nodes(N);
    for (int i = 0; i < N; ++i) {
      cin >> nodes[i];
    }
    sort(nodes.begin(), nodes.end(), [&](const int &x, const int &y) -> bool {
      return tin[x] < tin[y];
    });
    nodes.emplace_back(nodes[0]);
    for (int i = 1; i <= N; ++i) {
      int lca = getLca(nodes[i - 1], nodes[i]);
      dp[nodes[i - 1]] += 1;
      dp[nodes[i]] += 1;
      dp[lca] -= 2;
    }
  }
  dfs2(1);
  vector<int> sol;
  for (int v = 2; v <= n; ++v) {
    if (dp[v] >= 2 * k) {
      sol.emplace_back(edge[v]);
    }
  }
  sort(sol.begin(), sol.end());
  cout << sol.size() << '\n';
  for (int index : sol) {
    cout << index << ' ';
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  precalc();
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  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