oj.uz

Submission #769998

# Submission time Handle Problem Language Result Execution time Memory
769998 2023-06-30T16:03:13 Z vjudge1 Paths (RMI21_paths) C++17
19 / 100
 600 ms 14840 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});
  }

  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.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 13 ms 340 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 11 ms 340 KB Output is correct

Subtask #3
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 13 ms 340 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 11 ms 340 KB Output is correct
8 Execution timed out 1088 ms 456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

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 13 ms 340 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 11 ms 340 KB Output is correct
8 Execution timed out 1088 ms 456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 14840 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 13 ms 340 KB Output is correct
4 Correct 13 ms 356 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 11 ms 340 KB Output is correct
8 Execution timed out 1088 ms 456 KB Time limit exceeded
9 Halted 0 ms 0 KB -