제출 #769998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769998		vjudge1	Paths (RMI21_paths)	C++17	19 / 100	1088 ms	14840 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<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) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, k;
  cin >> n >> k;

  vector<vector<array<long long, 2>>> adj(n);

  for (int i = 0; i < n - 1; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    adj[u].push_back({v, c});
    adj[v].push_back({u, c});
  }

  function<bool(int, int, int)> Remove = [&](int u, int prev, int to) {
    if (u == to) {
      return true;  
    }

    for (int i = 0; i < (int) adj[u].size(); i++) {
      int v = adj[u][i][0];

      if (v == prev) {
        continue;
      }

      if (Remove(v, u, to)) {
        adj[u][i][1] = 0;
        return true;
      }
    }
    return false;
  };

  long long best = 0;
  int nxt = -1;

  function<void(int, int, long long)> Dfs = [&](int u, int prev, long long sumAlongPath) {
    if (sumAlongPath > best) {
      best = sumAlongPath;
      nxt = u;
    }
    
    for (auto v : adj[u]) {
      if (v[0] == prev) {
        continue;
      }
      Dfs(v[0], u, sumAlongPath + v[1]);
    }
  };

  for (int root = 0; root < n; root++) {
    vector<vector<array<long long, 2>>> tmp = adj;

    long long res = 0;

    for (int j = 0; j < k; j++) {
      Dfs(root, -1, 0);

      if (nxt == -1) {
        break;
      }
      res += best;

      Remove(root, -1, nxt);
      best = 0; 
      nxt = -1;
    }

    cout << res << '\n';
    swap(adj, tmp);
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32