Submission #404774

#	Time	Username	Problem	Language	Result	Execution time	Memory
404774		rama_pang	Railway (BOI17_railway)	C++17	100 / 100	242 ms	36272 KiB

railway

#include <bits/stdc++.h>
using namespace std;

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

  int N, M, K;
  cin >> N >> M >> K;

  vector<vector<int>> adj(N);
  map<pair<int, int>, int> edge_id;
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    edge_id[{u, v}] = i;
    edge_id[{v, u}] = i;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  vector<int> st(N);
  vector<int> siz(N);
  vector<int> par(N);
  vector<int> root(N);
  vector<int> depth(N);

  const auto DfsInit = [&](const auto &self, int u, int p) -> void {
    if (p != -1) {
      adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
    }
    par[u] = p;
    siz[u] = 1;
    for (auto &v : adj[u]) {
      depth[v] = depth[u] + 1;
      self(self, v, u);
      siz[u] += siz[v];
      if (siz[v] > siz[adj[u][0]]) {
        swap(v, adj[u][0]);
      }
    }
  };

  const auto DfsHld = [&](const auto &self, int u) -> void {
    static int timer = 0;
    st[u] = timer++;
    for (auto v : adj[u]) {
      root[v] = v == adj[u][0] ? root[u] : v;
      self(self, v);
    }
  };

  DfsInit(DfsInit, 0, -1);
  DfsHld(DfsHld, 0);

  const auto Lca = [&](int x, int y) {
    while (root[x] != root[y]) {
      if (depth[root[x]] > depth[root[y]]) swap(x, y);
      y = par[root[y]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    return x;
  };

  vector<int> cnt(N);
  vector<int> answer;
  const auto DfsCnt = [&](const auto &self, int u) -> void {
    for (auto v : adj[u]) {
      self(self, v);
      if (cnt[v] >= K) {
        answer.emplace_back(edge_id[{u, v}]);
      }
      cnt[u] += cnt[v];
    }
  };

  while (M--) {
    int s;
    cin >> s;
    vector<int> ls;
    for (int i = 0; i < s; i++) {
      int u;
      cin >> u;
      ls.emplace_back(--u);
    }
    sort(begin(ls), end(ls), [&](int i, int j) {
      return st[i] < st[j];
    });
    for (int i = 0; i < s; i++) {
      int u = ls[(i + 0) % s];
      int v = ls[(i + 1) % s];
      cnt[v]++;
      cnt[Lca(u, v)]--;
    }
  }

  DfsCnt(DfsCnt, 0);

  cout << answer.size() << '\n';
  sort(begin(answer), end(answer));
  for (int i = 0; i < int(answer.size()); i++) {
    cout << answer[i] << " \n"[i + 1 == answer.size()];
  }
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:103:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     cout << answer[i] << " \n"[i + 1 == answer.size()];
      |                                ~~~~~~^~~~~~~~~~~~~~~~

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