oj.uz

Submission #1088878

# Submission time Handle Problem Language Result Execution time Memory
1088878 2024-09-15T11:58:22 Z juicy Museum (CEOI17_museum) C++17
100 / 100
 507 ms 784472 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e4;

int n, k, x;
int a[N][N + 1], b[N][N + 1];
vector<array<int, 2>> g[N];

int dfs(int u, int p) {
  int x = 1;
  a[u][1] = b[u][1] = 0;
  for (auto [v, w] : g[u]) {
    if (v ^ p) {
      int y = dfs(v, u);
      for (int i = x; i; --i) {
        for (int j = y; j; --j) {
          a[u][i + j] = min(a[u][i + j], a[u][i] + a[v][j] + 2 * w);
          b[u][i + j] = min({b[u][i + j], a[u][i] + b[v][j] + w, b[u][i] + a[v][j] + 2 * w});
        }
      }
      x += y;
    }
  }
  return x;
}

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

  cin >> n >> k >> x; --x;
  for (int i = 1; i < n; ++i) {
    int u, v, c; cin >> u >> v >> c; --u, --v;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }  
  memset(a, 0x3f, sizeof(a));
  memset(b, 0x3f, sizeof(b));
  dfs(x, x);
  cout << b[x][k];
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 783444 KB Output is correct
2 Correct 364 ms 783312 KB Output is correct
3 Correct 387 ms 783480 KB Output is correct
4 Correct 349 ms 783696 KB Output is correct
5 Correct 350 ms 783448 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 783956 KB Output is correct
2 Correct 458 ms 783944 KB Output is correct
3 Correct 506 ms 784448 KB Output is correct
4 Correct 427 ms 784112 KB Output is correct
5 Correct 421 ms 783908 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 783956 KB Output is correct
2 Correct 458 ms 783944 KB Output is correct
3 Correct 506 ms 784448 KB Output is correct
4 Correct 427 ms 784112 KB Output is correct
5 Correct 421 ms 783908 KB Output is correct
6 Correct 425 ms 783956 KB Output is correct
7 Correct 441 ms 784208 KB Output is correct
8 Correct 485 ms 783992 KB Output is correct
9 Correct 464 ms 784068 KB Output is correct
10 Correct 487 ms 784080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 783444 KB Output is correct
2 Correct 364 ms 783312 KB Output is correct
3 Correct 387 ms 783480 KB Output is correct
4 Correct 349 ms 783696 KB Output is correct
5 Correct 350 ms 783448 KB Output is correct
6 Correct 445 ms 783956 KB Output is correct
7 Correct 458 ms 783944 KB Output is correct
8 Correct 506 ms 784448 KB Output is correct
9 Correct 427 ms 784112 KB Output is correct
10 Correct 421 ms 783908 KB Output is correct
11 Correct 425 ms 783956 KB Output is correct
12 Correct 441 ms 784208 KB Output is correct
13 Correct 485 ms 783992 KB Output is correct
14 Correct 464 ms 784068 KB Output is correct
15 Correct 487 ms 784080 KB Output is correct
16 Correct 472 ms 783912 KB Output is correct
17 Correct 462 ms 784212 KB Output is correct
18 Correct 454 ms 784208 KB Output is correct
19 Correct 482 ms 783952 KB Output is correct
20 Correct 438 ms 784096 KB Output is correct
21 Correct 451 ms 784332 KB Output is correct
22 Correct 456 ms 783952 KB Output is correct
23 Correct 507 ms 783884 KB Output is correct
24 Correct 447 ms 783884 KB Output is correct
25 Correct 476 ms 784472 KB Output is correct