Submission #756827

#	Time	Username	Problem	Language	Result	Execution time	Memory
756827		NeroZein	Railway (BOI17_railway)	C++17	100 / 100	108 ms	33376 KiB

railway

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

template<typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
  int n; 
  F func; 
  vector<vector<T>> mat;
  SparseTable () {}
  SparseTable (const vector<T>& a, F f) : func(f) {
    n = (int) a.size(); 
    int max_log = 32 - __builtin_clz(n); 
    mat.resize(max_log);
    mat[0] = a; 
    for (int j = 1; j < max_log; ++j) {
      mat[j].resize(n - (1 << j) + 1); 
      for (int i = 0; i <= n - (1 << j); ++i) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T get (int from, int to) {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 31 - __builtin_clz(to - from + 1); 
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

const int N = 100005;

vector<pair<int, int>> g[N]; 

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }
  int idd = 0; 
  vector<int> f(n + 1); 
  vector<int> dep(n + 1); 
  vector<int> o(2 * n - 1); 
  function<void(int, int)> Dfs = [&](int v, int p) {
    f[v] = idd;
    o[idd++] = v;
    for (auto [u, i] : g[v]) {
      if (u == p) {
        continue;
      }
      dep[u] = dep[v] + 1; 
      Dfs(u, v); 
      o[idd++] = v; 
    }
  }; 
  Dfs(1, 1); 
  SparseTable<int> spa(o, [&](int x, int y) { return dep[x] < dep[y] ? x : y; });
  auto Lca = [&](int u, int v) {
    u = f[u], v = f[v];
    if (u > v) swap(u, v);
    return spa.get(u, v); 
  };
  vector<int> dp(n + 1); 
  auto Add = [&](int u, int v) {
    dp[u]++;
    dp[v]++;
    dp[Lca(u, v)] -= 2; 
  };
  for (int i = 0; i < m; ++i) {
    int s;
    cin >> s;
    vector<int> a(s);
    for (int j = 0; j < s; ++j) {
      cin >> a[j];
    }
    sort(a.begin(), a.end(), [&](int x, int y) { return f[x] < f[y]; }); 
    for (int j = 1; j <= s; ++j) {
      Add(a[j - 1], a[j % s]); 
    }
  }
  vector<int> ans;
  function<int(int, int)> Dfs2 = [&](int v, int p) {
    int ret = dp[v];
    for (auto [u, i] : g[v]) {
      if (u == p) {
        continue;
      }
      int c = Dfs2(u, v); 
      ret += c;
      if (c / 2 >= k) {
        ans.push_back(i + 1); 
      }
    }
    return ret;
  }; 
  Dfs2(1, 1); 
  sort(ans.begin(), ans.end()); 
  cout << ans.size() << '\n';
  for (int i = 0; i < (int) ans.size(); ++i) {
    cout << ans[i] << " \n"[i == (int) ans.size() - 1]; 
  }
  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