oj.uz

Submission #1096299

# Submission time Handle Problem Language Result Execution time Memory
1096299 2024-10-04T08:52:15 Z vjudge1 Museum (CEOI17_museum) C++17
20 / 100
 347 ms 1048576 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+500;

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];
int64_t 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 856 KB Output is correct
2 Correct 1 ms 856 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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 347 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 347 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 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 Runtime error 347 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -