Submission #1285383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285383		peanut	Railway (BOI17_railway)	C++20	100 / 100	83 ms	23332 KiB

railway

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

int n, m, k;
vector<int> adj[maxn];
int timer;
int val[maxn];
int tin[maxn], up[maxn][20], depth[maxn];
pair<int, int> edges[maxn];
int id[maxn];
vector<int> ans;
void dfs(int u, int p)
{
  tin[u] = ++timer;
  for (auto v : adj[u])
  {
    if (v == p) continue;
    depth[v] = depth[u] + 1;
    up[v][0] = u;
    for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i-1]][i-1];
    dfs(v, u);
  }
}
int lca(int u, int v)
{
  if (depth[u] < depth[v]) swap(u, v);
  int k = depth[u] - depth[v];
  for (int i = 0; i < 20; ++i) if (k >> i & 1) u = up[u][i];
  if (u == v) return u;
  for (int i = 19; i >= 0; --i)
  {
    if (up[u][i] != up[v][i])
    {
      u = up[u][i];
      v = up[v][i];
    }
  }
  return up[u][0];
}
void dfs2(int u, int p)
{
  for (auto v : adj[u])
  {
    if (v == p) continue;
    dfs2(v, u);
    val[u] += val[v];
  }
  if (u != 1 && val[u] / 2 >= k) ans.push_back(id[u]);
}
int main()
{
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i)
  {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edges[i] = {u, v};
  }
  dfs(1, 0);
  for (int i = 1; i < n; ++i)
  {
    int u = edges[i].first;
    int v = edges[i].second;
    if (depth[u] < depth[v]) swap(u, v);
    id[u] = i;
  }
  for (int i = 1; i <= m; ++i)
  {
    int s; cin >> s;
    vector<int> nd(s);
    for (int j = 0; j < s; ++j) cin >> nd[j];
    sort(nd.begin(), nd.end(), [&](int u, int v){return tin[u] < tin[v];});
    for (int j = 0; j < s; ++j)
    {
      int u = nd[j];
      int v = nd[(j+1)%s];
      val[u]++;
      val[v]++;
      val[lca(u, v)] -= 2;
    }
  }
  dfs2(1, 0);
  sort(ans.begin(), ans.end());
  cout << ans.size() << '\n';
  for (auto i : ans) cout << i << ' ';
  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