oj.uz

Submission #646004

# Submission time Handle Problem Language Result Execution time Memory
646004 2022-09-28T13:22:34 Z Alex_tz307 Paths (RMI21_paths) C++17
100 / 100
 417 ms 36656 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
int n, k;
int64_t sumK, sol[1 + kN];
pair<int64_t, int> dmax[1 + kN];
vector<pair<int, int>> g[1 + kN];
set<pair<int64_t, int>> paths[1 + kN];
multiset<int64_t> low, big;

void fix() {
  while ((int)big.size() < k && !low.empty()) {
    auto it = --low.end();
    big.emplace(*it);
    sumK += *it;
    low.erase(it);
  }

  if (low.empty() || big.empty()) {
    return;
  }

  int64_t last = *(--low.end()), first = *big.begin();
  while (first < last) {
    big.erase(big.begin());
    low.erase(--low.end());
    low.emplace(first);
    sumK -= first;
    big.emplace(last);
    sumK += last;
    last = *(--low.end());
    first = *big.begin();
  }
}

void add(int64_t x) {
  if ((int)big.size() < k) {
    big.emplace(x);
    sumK += x;
  } else {
    low.emplace(x);
    fix();
  }
}

void rem(int64_t x) {
  if (low.count(x)) {
    low.erase(low.find(x));
  } else {
    big.erase(big.find(x));
    sumK -= x;
    fix();
  }
}

void dfs1(int u, int par) {
  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;

    if (v != par) {
      dfs1(v, u);

      if (paths[v].empty()) {
        paths[u].emplace(w, v);
      } else {
        paths[u].emplace((--paths[v].end())->first + w, v);
      }
    }
  }
}

void dfs2(int u, int par) {
  sol[u] = sumK;

  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;

    if (v != par) {
      auto it1 = --paths[u].end();
      pair<int64_t, int> path1, removed{-1, -1};

      if (it1->second == v) {
        if ((int)paths[u].size() == 1) {
          path1 = {w, u};
        } else {
          auto it2 = --it1;
          path1 = {it2->first + w, u};
          removed = *it2;
        }
      } else {
        path1 = {it1->first + w, u};
        removed = *it1;
      }

      paths[v].emplace(path1);
      add(path1.first);
      if (removed.first != -1) {
        rem(removed.first);
      }

      pair<int64_t, int> path2{dmax[v].first + w, v};
      rem(path2.first);
      paths[v].emplace(dmax[v]);
      add(dmax[v].first);

      dfs2(v, u);

      rem(path1.first);
      if (removed.first != -1) {
        add(removed.first);
      }

      add(path2.first);
      rem(dmax[v].first);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  dfs1(1, 0);

  for (int i = 1; i <= n; ++i) {
    if (!paths[i].empty()) {
      auto it = *(--paths[i].end());
      dmax[i] = it;
      if (i != 1) {
        paths[i].erase(it);
      }
    }

    for (auto it : paths[i]) {
      add(it.first);
    }
  }

  dfs2(1, 0);

  for (int i = 1; i <= n; ++i) {
    cout << sol[i] << '\n';
  }

  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7440 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7440 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 7652 KB Output is correct
9 Correct 6 ms 7636 KB Output is correct
10 Correct 7 ms 7512 KB Output is correct
11 Correct 6 ms 7636 KB Output is correct
12 Correct 5 ms 7520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7440 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 7652 KB Output is correct
9 Correct 6 ms 7636 KB Output is correct
10 Correct 7 ms 7512 KB Output is correct
11 Correct 6 ms 7636 KB Output is correct
12 Correct 5 ms 7520 KB Output is correct
13 Correct 9 ms 7892 KB Output is correct
14 Correct 7 ms 7892 KB Output is correct
15 Correct 8 ms 7764 KB Output is correct
16 Correct 7 ms 7892 KB Output is correct
17 Correct 8 ms 7772 KB Output is correct
18 Correct 7 ms 7764 KB Output is correct
19 Correct 8 ms 7892 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 33120 KB Output is correct
2 Correct 310 ms 36288 KB Output is correct
3 Correct 212 ms 28788 KB Output is correct
4 Correct 313 ms 33744 KB Output is correct
5 Correct 313 ms 34976 KB Output is correct
6 Correct 328 ms 34220 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7440 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 7652 KB Output is correct
9 Correct 6 ms 7636 KB Output is correct
10 Correct 7 ms 7512 KB Output is correct
11 Correct 6 ms 7636 KB Output is correct
12 Correct 5 ms 7520 KB Output is correct
13 Correct 9 ms 7892 KB Output is correct
14 Correct 7 ms 7892 KB Output is correct
15 Correct 8 ms 7764 KB Output is correct
16 Correct 7 ms 7892 KB Output is correct
17 Correct 8 ms 7772 KB Output is correct
18 Correct 7 ms 7764 KB Output is correct
19 Correct 8 ms 7892 KB Output is correct
20 Correct 329 ms 33120 KB Output is correct
21 Correct 310 ms 36288 KB Output is correct
22 Correct 212 ms 28788 KB Output is correct
23 Correct 313 ms 33744 KB Output is correct
24 Correct 313 ms 34976 KB Output is correct
25 Correct 328 ms 34220 KB Output is correct
26 Correct 399 ms 34152 KB Output is correct
27 Correct 343 ms 36128 KB Output is correct
28 Correct 384 ms 36656 KB Output is correct
29 Correct 226 ms 28876 KB Output is correct
30 Correct 364 ms 34260 KB Output is correct
31 Correct 417 ms 31964 KB Output is correct
32 Correct 356 ms 35272 KB Output is correct
33 Correct 362 ms 34164 KB Output is correct
34 Correct 186 ms 28224 KB Output is correct
35 Correct 378 ms 34316 KB Output is correct
36 Correct 300 ms 36080 KB Output is correct