oj.uz

Submission #1115120

# Submission time Handle Problem Language Result Execution time Memory
1115120 2024-11-20T04:38:24 Z _Sherbiny Museum (CEOI17_museum) C++17
20 / 100
 5 ms 2640 KB 
// Author: _Sherbiny

#include "bits/stdc++.h"
using namespace std;

#ifdef DBG
#include "./debug.h"
#else
#define dbg(...)
#endif

typedef long long ll;
#define endl '\n'
#define int ll
//==================//
const int N = 5001;
int tot[N], n, k;

array<int, 2> oo;
vector<array<int, 2>> dp[N];
vector<vector<pair<int, int>>> adj;

void merge(int u, int v, int c) {
    auto ret = dp[u];
    ret.resize(dp[u].size() + dp[v].size() - 1, oo);

    for(int i = 1; i < dp[u].size(); ++i)
        for(int j = 1; j < dp[v].size(); ++j) {
            ret[i + j][0] = min(ret[i + j][0], dp[u][i][0] + dp[v][j][0] + c * 2);
            ret[i + j][1] = min({ret[i + j][1], dp[u][i][1] + dp[v][j][0] + c * 2, dp[u][i][0] + dp[v][j][1] + c});
        }

    swap(ret, dp[u]);
}

void go(int u, int p = 0) {
    for(auto[v, c]: adj[u])
        if(v != p) go(v, u);

    dp[u].assign(2, {});
    for(auto &[v, c]: adj[u])
        if(v != p) merge(u, v, c);
}

void magic() {
    cin >> n >> k;
    int x; cin >> x;
    oo.fill(2e18);

    adj.assign(n + 1, {});
    for (int i = 0; i < n - 1; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    go(x);
    cout << dp[x][k][1];
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) magic();
}

Compilation message

museum.cpp: In function 'void merge(ll, ll, ll)':
museum.cpp:27:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 1; i < dp[u].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~
museum.cpp:28:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j = 1; j < dp[v].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 532 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 2640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 2640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 532 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Runtime error 5 ms 2640 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -