oj.uz

Submission #1096302

# Submission time Handle Problem Language Result Execution time Memory
1096302 2024-10-04T08:54:20 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 857 ms 784848 KB 
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define minimize(a,b) a=min(a,b)

const int INF = 1e9+7;
const int MAXN = 1e4+5;

int n, k, root;
struct Edge
{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
    int other(const int x){return x^u^v;}
} edge[MAXN];

vector<int> e[MAXN];

int sz[MAXN];
int dp[MAXN][2][MAXN];


void dfs(int u=root, int p=0){
    dp[u][0][1] = dp[u][1][1] = 0;
    sz[u] = 1;

    for(int &z : e[u]){
        int v = edge[z].other(u),
            w = edge[z].w;
        if(p==v)continue;

        dfs(v, u);
        for(int szu = sz[u]; szu>=0; --szu)
        for(int szv = sz[v]; szv>=0; --szv){
            minimize(dp[u][0][szu+szv], dp[u][0][szu] + dp[v][0][szv] + 2*w);
            minimize(dp[u][1][szu+szv], dp[u][0][szu] + dp[v][1][szv] + w);
            minimize(dp[u][1][szu+szv], dp[u][1][szu] + dp[v][0][szv] + 2*w);
        }
        sz[u]+=sz[v];
    }

    

}


signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("*.inp", "r")){
        freopen("*.inp", "r",stdin);
        freopen("*.out", "w",stdout);
    }


    cin >> n >> k >> root;
    for(int u, v, i=1; i<n; ++i){
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        e[edge[i].u].emplace_back(i);
        e[edge[i].v].emplace_back(i);
    }
    
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= n; ++j)
            dp[i][0][j] = dp[i][1][j] = INF;
    dfs();
    cout << min(dp[root][0][k], dp[root][1][k]);
    

    return 0;
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:61:13: warning: unused variable 'u' [-Wunused-variable]
   61 |     for(int u, v, i=1; i<n; ++i){
      |             ^
museum.cpp:61:16: warning: unused variable 'v' [-Wunused-variable]
   61 |     for(int u, v, i=1; i<n; ++i){
      |                ^
museum.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("*.inp", "r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
museum.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("*.out", "w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 784464 KB Output is correct
2 Correct 403 ms 784212 KB Output is correct
3 Correct 507 ms 784780 KB Output is correct
4 Correct 432 ms 784576 KB Output is correct
5 Correct 397 ms 784272 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 784464 KB Output is correct
2 Correct 403 ms 784212 KB Output is correct
3 Correct 507 ms 784780 KB Output is correct
4 Correct 432 ms 784576 KB Output is correct
5 Correct 397 ms 784272 KB Output is correct
6 Correct 410 ms 784476 KB Output is correct
7 Correct 454 ms 784504 KB Output is correct
8 Correct 857 ms 784588 KB Output is correct
9 Correct 699 ms 784472 KB Output is correct
10 Correct 426 ms 784724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 406 ms 784464 KB Output is correct
7 Correct 403 ms 784212 KB Output is correct
8 Correct 507 ms 784780 KB Output is correct
9 Correct 432 ms 784576 KB Output is correct
10 Correct 397 ms 784272 KB Output is correct
11 Correct 410 ms 784476 KB Output is correct
12 Correct 454 ms 784504 KB Output is correct
13 Correct 857 ms 784588 KB Output is correct
14 Correct 699 ms 784472 KB Output is correct
15 Correct 426 ms 784724 KB Output is correct
16 Correct 399 ms 784208 KB Output is correct
17 Correct 390 ms 784288 KB Output is correct
18 Correct 429 ms 784468 KB Output is correct
19 Correct 704 ms 784448 KB Output is correct
20 Correct 413 ms 784300 KB Output is correct
21 Correct 432 ms 784656 KB Output is correct
22 Correct 396 ms 784460 KB Output is correct
23 Correct 700 ms 784468 KB Output is correct
24 Correct 405 ms 784472 KB Output is correct
25 Correct 454 ms 784848 KB Output is correct