Submission #1096302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096302		vjudge1	Museum (CEOI17_museum)	C++17	100 / 100	857 ms	784848 KiB

museum

#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 (stderr)

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20