Submission #1128316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128316		d4xn	Railway (BOI17_railway)	C++17	100 / 100	149 ms	33352 KiB

railway

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

const int N = 1e5;

int n, m, k, dep[N], cnt[N], curr[N], ans[N];
pair<int, int> p[N];
vector<int> a[N];
vector<pair<int, int>> adj[N];
set<int> st[N];

void dfs(int x, int par, int preIdx) {
  p[x] = make_pair(par, preIdx);
  a[dep[x]].push_back(x);
  for (auto &[y, idx] : adj[x]) {
    if (y == par) continue;

    dep[y] = dep[x]+1;
    dfs(y, x, idx);
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  memset(curr, 0, sizeof(curr));
  memset(ans, 0, sizeof(ans));

  cin >> n >> m >> k;
  for (int i = 0; i < n-1; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;

    adj[x].push_back(make_pair(y, i));
    adj[y].push_back(make_pair(x, i));
  }

  for (int i = 0; i < m; i++) {
    int x; cin >> x;
    cnt[i] = x;
    for (int j = 0; j < x; j++) {
      int y; cin >> y; y--;
      st[y].insert(i);
    }
  }

  dep[0] = 0;
  dfs(0, 0, 0);

  for (int i = n-1; i > 0; i--) {
    for (int &x : a[i]) {
      // sumar sz a la arista hacia mi padre
      int sz = st[x].size();
      ans[p[x].second] += sz;

      int pp = p[x].first;
      if (st[x].size() > st[pp].size()) st[x].swap(st[pp]);

      while (!st[x].empty()) {
        int y = *st[x].begin();
        st[x].erase(st[x].begin());

        auto it = st[pp].find(y);
        if (it != st[pp].end()) {
          if (++curr[y] + 1 == cnt[y]) st[pp].erase(it);
        }
        else {
          st[pp].insert(y);
        }
      }
    }
  }

  vector<int> edges;
  for (int i = 0; i < n-1; i++) {
    if (ans[i] >= k) {
      edges.push_back(i);
    } 
  }

  cout << edges.size() << "\n";
  for (int& i : edges) {
    cout << i+1 << " ";
  }
  cout << "\n";
}

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