oj.uz

답안 #223918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223918 2020-04-16T20:47:40 Z Leonardo_Paes Museum (CEOI17_museum) C++17
100 / 100
 433 ms 169768 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define f first
#define s second
 
const int maxn = 1e4+10, inf = 0x3f3f3f3f;
 
typedef pair<int,int> pii;
 
int n, k, x, siz[maxn], dp[maxn][maxn][2];
 
vector<pii> grafo[maxn];
 
void dfs(int u, int p = 0){
    siz[u] = 1;
 
    for(auto v : grafo[u]){
        if(v.f == p) continue;
 
        dfs(v.f, u);
 
        siz[u] += siz[v.f];
    }
}
 
int solve(int u, int p = 0){
    int sizes = 1, d;
 
    for(auto v : grafo[u]){
        if(v.f == p) continue;
 
        solve(v.f, u);
 
        sizes += siz[v.f];
 
        d = v.s;
 
        for(int i=sizes; i>=2; i--){
            for(int j=max(0, i-sizes+siz[v.f]); j<=min(i, siz[v.f]); j++){
                dp[u][i][0] = min({dp[u][i][0], dp[u][i-j][0] + dp[v.f][j][1]
                + 2*d, dp[u][i-j][1] + dp[v.f][j][0] + d});
                dp[u][i][1] = min({dp[u][i][1], dp[u][i-j][1] + dp[v.f][j][1] + 2*d});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
    cin >> n >> k >> x;
 
    for(int i=1; i<n; i++){
        int u, v, d;
 
        cin >> u >> v >> d;
 
        grafo[u].push_back({v, d});
        grafo[v].push_back({u, d});
    }
 
    dfs(x);
 
    for(int i=1; i<=n; i++){
        for(int j=2; j<=siz[i]; j++){
            dp[i][j][0] = dp[i][j][1] = inf;
        }
    }
 
    solve(x);
 
    cout << dp[x][k][0] << endl;
 
    return 0;
}

Compilation message

museum.cpp: In function 'int solve(int, int)':
museum.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 28808 KB Output is correct
2 Correct 163 ms 29056 KB Output is correct
3 Correct 357 ms 165040 KB Output is correct
4 Correct 234 ms 73084 KB Output is correct
5 Correct 184 ms 40336 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 28808 KB Output is correct
2 Correct 163 ms 29056 KB Output is correct
3 Correct 357 ms 165040 KB Output is correct
4 Correct 234 ms 73084 KB Output is correct
5 Correct 184 ms 40336 KB Output is correct
6 Correct 165 ms 23424 KB Output is correct
7 Correct 285 ms 107872 KB Output is correct
8 Correct 433 ms 2808 KB Output is correct
9 Correct 334 ms 2816 KB Output is correct
10 Correct 177 ms 3960 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 165 ms 28808 KB Output is correct
7 Correct 163 ms 29056 KB Output is correct
8 Correct 357 ms 165040 KB Output is correct
9 Correct 234 ms 73084 KB Output is correct
10 Correct 184 ms 40336 KB Output is correct
11 Correct 165 ms 23424 KB Output is correct
12 Correct 285 ms 107872 KB Output is correct
13 Correct 433 ms 2808 KB Output is correct
14 Correct 334 ms 2816 KB Output is correct
15 Correct 177 ms 3960 KB Output is correct
16 Correct 162 ms 29560 KB Output is correct
17 Correct 166 ms 29432 KB Output is correct
18 Correct 244 ms 82680 KB Output is correct
19 Correct 360 ms 2936 KB Output is correct
20 Correct 165 ms 4856 KB Output is correct
21 Correct 267 ms 105848 KB Output is correct
22 Correct 161 ms 29176 KB Output is correct
23 Correct 351 ms 2808 KB Output is correct
24 Correct 161 ms 4728 KB Output is correct
25 Correct 369 ms 169768 KB Output is correct