oj.uz

Submission #770002

# Submission time Handle Problem Language Result Execution time Memory
770002 2023-06-30T16:14:10 Z vjudge1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 24388 KB 
#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});
  }

  vector<long long> to(n);
  vector<int> depth(n);
  vector<int> in(n);
  vector<int> leaves;
  vector<int> euler_tour;

  function<void(int, int, long long)> Dfs = [&](int u, int prev, long long sumAlongPath) {
    to[u] = sumAlongPath;
    bool is_leaf = true;

    in[u] = (int) euler_tour.size();
    euler_tour.push_back(u);

    for (auto v : adj[u]) {
      if (v[0] == prev) {
        continue;
      }
      is_leaf = false;
      depth[v[0]] = depth[u] + 1;
      Dfs(v[0], u, sumAlongPath + v[1]);
      euler_tour.push_back(u);
    }

    if (is_leaf) {
      leaves.push_back(u);
    }
  };

  auto Clear = [&]() {
    to.clear();
    to.resize(n);
    depth.clear();
    depth.resize(n);
    in.clear();
    in.resize(n);
    leaves.clear();
    euler_tour.clear();
  };

  for (int root = 0; root < n; root++) {
    Clear();
    Dfs(root, -1, 0LL);

    SparseTable<int> st(euler_tour, [&](int x, int y) {
      if (depth[x] < depth[y]) {
        return x;
      }
      return y;
    });

    auto lca = [&](int x, int y) {
      if (in[x] > in[y]) {
        swap(x, y);
      }
      return st.get(in[x], in[y]);
    };

    vector<int> current_lca(n, root);

    long long res = 0;

    int len = (int) leaves.size();

    for (int j = 0; j < min(len, k); j++) {
      long long best = 0;
      int toUse = -1;
      for (int i = 0; i < (int) leaves.size(); i++) {
        if (best < to[leaves[i]]) {
          best = to[leaves[i]];
          toUse = leaves[i];
        }
      }
      if (toUse == -1) {
        break;
      }
      res += best;

      vector<int> nleaves;
      for (int i = 0; i < (int) leaves.size(); i++) {
        if (leaves[i] == toUse) {
          continue;
        }
        nleaves.push_back(leaves[i]);
        int nlca = lca(toUse, leaves[i]);
        if (depth[nlca] > depth[current_lca[leaves[i]]]) {
          to[leaves[i]] += to[current_lca[leaves[i]]];
          to[leaves[i]] -= to[nlca];
          current_lca[leaves[i]] = nlca;
        }
      }

      swap(leaves, nleaves);
    }

    cout << res << '\n';
  }
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 5 ms 356 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 5 ms 356 KB Output is correct
8 Correct 497 ms 616 KB Output is correct
9 Correct 189 ms 568 KB Output is correct
10 Correct 115 ms 532 KB Output is correct
11 Correct 573 ms 528 KB Output is correct
12 Correct 227 ms 520 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 5 ms 356 KB Output is correct
8 Correct 497 ms 616 KB Output is correct
9 Correct 189 ms 568 KB Output is correct
10 Correct 115 ms 532 KB Output is correct
11 Correct 573 ms 528 KB Output is correct
12 Correct 227 ms 520 KB Output is correct
13 Execution timed out 1088 ms 760 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 24388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 5 ms 356 KB Output is correct
8 Correct 497 ms 616 KB Output is correct
9 Correct 189 ms 568 KB Output is correct
10 Correct 115 ms 532 KB Output is correct
11 Correct 573 ms 528 KB Output is correct
12 Correct 227 ms 520 KB Output is correct
13 Execution timed out 1088 ms 760 KB Time limit exceeded
14 Halted 0 ms 0 KB -