Submission #790179

#	Time	Username	Problem	Language	Result	Execution time	Memory
790179		tch1cherin	Railway (BOI17_railway)	C++17	100 / 100	152 ms	37060 KiB

railway

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

const int MAX_N = 1e5 + 5;
vector<pair<int, int>> G[MAX_N];
map<int, int> cnt[MAX_N];
int S[MAX_N], bad[MAX_N];
vector<int> ans;

void DFS(int u, int p, int k) {
  for (auto [key, value] : cnt[u]) {
    bad[u] += value == S[key]; 
  }
  for (auto [v, i] : G[u]) {
    if (i != p) {
      DFS(v, i, k);
      if (cnt[u].size() < cnt[v].size()) {
        swap(cnt[u], cnt[v]);
        swap(bad[u], bad[v]);
      }
      for (auto [key, value] : cnt[v]) {
        cnt[u][key] += value;
        bad[u] += cnt[u][key] == S[key];
      }
    }
  }
  if ((int)cnt[u].size() - bad[u] >= k) {
    ans.push_back(p);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, K;
  cin >> N >> M >> K;
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back({v, i});
    G[v].push_back({u, i});
  }
  for (int i = 0; i < M; i++) {
    cin >> S[i];
    for (int j = 0; j < S[i]; j++) {
      int v;
      cin >> v;
      v--;
      cnt[v][i]++;
    }
  }
  DFS(0, -1, K);
  sort(ans.begin(), ans.end());
  int L = (int)ans.size();
  cout << L << "\n";
  for (int i = 0; i < L; i++) {
    cout << 1 + ans[i] << " \n"[i + 1 == L];
  }
}

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