oj.uz

Submission #862101

# Submission time Handle Problem Language Result Execution time Memory
862101 2023-10-17T14:08:50 Z sleepntsheep Museum (CEOI17_museum) C++17
100 / 100
 393 ms 777160 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 10002
#define ALL(x) x.begin(), x.end()

int dp[N][N][2];

int n, k, x, sz[N];
vector<pair<int, int>> g[N];

/*
 * at, take, comebacktonode
 *
 * dp[u][j][1] = min (t1 + t2 + ... + td == j - 1) 
 *              ( 2w + dp[v][j][1] )
 * dp[u][j][0] = min (t1 + t2 + ... + td == j - 1)
 *              (dp[v1][t1][1]+2*w1 + ... + dp[vd-1][td-1][1]+2*wd-1) + dp[vd][td][0] + wd
 * 
 * ans = dp[x][k][0]
 */

void dfs(int u, int p)
{
    sz[u] = 1;
    for (auto [w, v] : g[u])
    {
        if (v == p) continue;
        dfs(v, u);
        for (int i = sz[u]; i >= 0; --i) for (int j = sz[v]; j >= 0; --j)
        {
            dp[u][i+j][1] = min(dp[u][i+j][1], 2*w + dp[v][j][1] + dp[u][i][1]);
            dp[u][i+j][0] = min(dp[u][i+j][0], 2*w + dp[v][j][1] + dp[u][i][0]);
            dp[u][i+j][0] = min(dp[u][i+j][0], w + dp[v][j][0] + dp[u][i][1]);
        }
        sz[u] += sz[v];
    }
}

int main()
{
    ShinLena;
    cin >> n >> k >> x;
    for (int i = 1, u, v, w; i < n; ++i)
        cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 1; i <= n; ++i) for (int j = 2; j <= k; ++j) dp[i][j][0] = dp[i][j][1] = 1e9;
    dfs(x, x);
    cout << dp[x][k][0];

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2480 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 356744 KB Output is correct
2 Correct 153 ms 449364 KB Output is correct
3 Correct 235 ms 510208 KB Output is correct
4 Correct 185 ms 469332 KB Output is correct
5 Correct 169 ms 517200 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 356744 KB Output is correct
2 Correct 153 ms 449364 KB Output is correct
3 Correct 235 ms 510208 KB Output is correct
4 Correct 185 ms 469332 KB Output is correct
5 Correct 169 ms 517200 KB Output is correct
6 Correct 163 ms 511828 KB Output is correct
7 Correct 210 ms 542692 KB Output is correct
8 Correct 327 ms 513876 KB Output is correct
9 Correct 260 ms 515664 KB Output is correct
10 Correct 172 ms 511936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2480 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 169 ms 356744 KB Output is correct
7 Correct 153 ms 449364 KB Output is correct
8 Correct 235 ms 510208 KB Output is correct
9 Correct 185 ms 469332 KB Output is correct
10 Correct 169 ms 517200 KB Output is correct
11 Correct 163 ms 511828 KB Output is correct
12 Correct 210 ms 542692 KB Output is correct
13 Correct 327 ms 513876 KB Output is correct
14 Correct 260 ms 515664 KB Output is correct
15 Correct 172 ms 511936 KB Output is correct
16 Correct 184 ms 543680 KB Output is correct
17 Correct 239 ms 655952 KB Output is correct
18 Correct 205 ms 553300 KB Output is correct
19 Correct 294 ms 539728 KB Output is correct
20 Correct 179 ms 567892 KB Output is correct
21 Correct 317 ms 772388 KB Output is correct
22 Correct 292 ms 772212 KB Output is correct
23 Correct 393 ms 775472 KB Output is correct
24 Correct 276 ms 776072 KB Output is correct
25 Correct 327 ms 777160 KB Output is correct