oj.uz

Submission #869486

# Submission time Handle Problem Language Result Execution time Memory
869486 2023-11-04T12:23:43 Z Cookie Museum (CEOI17_museum) C++14
100 / 100
 349 ms 784740 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HCN.INP");
ofstream fout("HCN.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
//using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e6 + 5, mxq = 2e5 + 5, sq = 350, mxv = 2e6 + 5;
const ll inf = 1e9;
int n, k, root;
int dp[10001][10001], sz[10001], dp2[10001][10001];
vt<pii>adj[10001];
void ckmin(int &a, int b){
    a = min(a, b);
}
void dfs(int s, int pre, int dep){
    dp[s][1] = 0; dp2[s][1] = -dep;
    sz[s] = 1;
    for(auto [i, w]: adj[s]){
        if(i != pre){
            dfs(i, s, dep + w);
            for(int j = sz[s] + sz[i]; j >= 1; j--){
                for(int take = max(1, j - sz[s]); take <= min(j, sz[i]); take++){
                    ckmin(dp[s][j], dp[s][j - take] + dp[i][take] + 2 * w);
                    ckmin(dp2[s][j], dp2[s][j - take] + dp[i][take] + 2 * w);
                    ckmin(dp2[s][j], dp[s][j - take] + dp2[i][take] + 2 * w);
                }
            }
            sz[s] += sz[i];
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> root;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            dp[i][j] = dp2[i][j] = inf;
        }
    }
    for(int i = 1; i < n; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w}); adj[v].pb({u, w});
    }
    dfs(root, -1, 0);
    
    cout << dp2[root][k];
    return(0);
}

Compilation message

museum.cpp: In function 'void dfs(int, int, int)':
museum.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [i, w]: adj[s]){
      |              ^

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 202336 KB Output is correct
2 Correct 156 ms 202580 KB Output is correct
3 Correct 345 ms 311900 KB Output is correct
4 Correct 209 ms 238928 KB Output is correct
5 Correct 194 ms 354060 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 202336 KB Output is correct
2 Correct 156 ms 202580 KB Output is correct
3 Correct 345 ms 311900 KB Output is correct
4 Correct 209 ms 238928 KB Output is correct
5 Correct 194 ms 354060 KB Output is correct
6 Correct 187 ms 694068 KB Output is correct
7 Correct 243 ms 745920 KB Output is correct
8 Correct 305 ms 741256 KB Output is correct
9 Correct 269 ms 783124 KB Output is correct
10 Correct 197 ms 782928 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 166 ms 202336 KB Output is correct
7 Correct 156 ms 202580 KB Output is correct
8 Correct 345 ms 311900 KB Output is correct
9 Correct 209 ms 238928 KB Output is correct
10 Correct 194 ms 354060 KB Output is correct
11 Correct 187 ms 694068 KB Output is correct
12 Correct 243 ms 745920 KB Output is correct
13 Correct 305 ms 741256 KB Output is correct
14 Correct 269 ms 783124 KB Output is correct
15 Correct 197 ms 782928 KB Output is correct
16 Correct 203 ms 783236 KB Output is correct
17 Correct 217 ms 783580 KB Output is correct
18 Correct 228 ms 783396 KB Output is correct
19 Correct 300 ms 783188 KB Output is correct
20 Correct 194 ms 783276 KB Output is correct
21 Correct 297 ms 784236 KB Output is correct
22 Correct 253 ms 784076 KB Output is correct
23 Correct 320 ms 783956 KB Output is correct
24 Correct 246 ms 784236 KB Output is correct
25 Correct 349 ms 784740 KB Output is correct