Submission #1048921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048921		duckindog	Railway (BOI17_railway)	C++17	100 / 100	52 ms	24248 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m, k;
vector<int> ad[N];
pair<int, int> edge[N];

int f[N][18],st[N], ed[N], it;
void dfs(int u, int p = -1) { 
  st[u] = ++it;

  for (int i = 1; i <= 17; ++i)
    f[u][i] = f[f[u][i - 1]][i - 1];

  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    f[v][0] = u;
    dfs(v, u);
  }

  ed[u] = it;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;

  for (int i = 17; i >= 0; --i) 
    if (!anc(f[u][i], v)) u = f[u][i];

  return f[u][0];
}

int bit[N];
void upd(int i, int x) { 
  for (; i <= n; i += i & -i) bit[i] += x;
}
int que(int i) { 
  int ret = 0;
  for (; i; i -= i & -i) ret += bit[i];
  return ret;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) { 
    int u, v; cin >> u >> v;
    edge[i] = {u, v};
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  dfs(f[1][0] = 1);
  while (m--) {
    int s; cin >> s;
    vector<int> vt(s);
    for (int i = 0; i < s; ++i) cin >> vt[i];
    sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
      return st[a] < st[b];
    });
    vt.push_back(vt[0]);
    for (int i = 1; i <= s; ++i) { 
      int u = vt[i - 1], v = vt[i];
      upd(st[lca(u, v)], -2);
      upd(st[u], 1);
      upd(st[v], 1);
    }
  }

  vector<int> answer;
  for (int i = 1; i < n; ++i) { 
    auto& [u, v] = edge[i];
    if (anc(v, u)) swap(u, v);
    if (que(ed[v]) - que(st[v] - 1) >= 2 * k) answer.push_back(i);
  }

  cout << answer.size() << "\n";
  for (const auto& x : answer) cout << x << " ";
  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