oj.uz

Submission #1098609

# Submission time Handle Problem Language Result Execution time Memory
1098609 2024-10-09T16:08:35 Z flyingkite Museum (CEOI17_museum) C++17
100 / 100
 696 ms 746324 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 1e4 + 2;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,k,x;
vector<pll>adj[N];
ll dp[N][N][2], sz[N], f[2][N][2];
void dfs(ll u, ll par){
    for(auto v : adj[u]){
        if(v.F == par) continue;
        dfs(v.F, u);
    }
    for(int i = 0; i <= k;i++){
        for(int j = 0; j <= 1;j++){
            for(int l = 0; l <= 1;l++) f[j][i][l] = inf;
        }
    }
    f[1][1][0] = 0;
    sz[u] = 1;
    for(int idx = 0; idx < adj[u].size();idx++){
        ll v = adj[u][idx].F, w = adj[u][idx].S;
        if(v == par){
            for(int i = 0; i <= sz[u];i++){
                for(int j = 0; j <= 1;j++) swap(f[0][i][j], f[1][i][j]);
            }
            continue;
        }
        for(int i = 0; i <= sz[u];i++){
            for(int j = 0; j <= sz[v];j++){
                f[idx & 1][i + j][0] = min(f[idx & 1][i + j][0], f[(idx & 1) ^ 1][i + j][0]);
                f[idx & 1][i + j][0] = min(f[idx & 1][i + j][0], f[(idx & 1) ^ 1][i][0] + dp[v][j][0] + 2 * w);
                f[idx & 1][i + j][1] = min(f[idx & 1][i + j][1], f[(idx & 1) ^ 1][i][0] + dp[v][j][1] + w);
                f[idx & 1][i + j][1] = min(f[idx & 1][i + j][1], f[(idx & 1) ^ 1][i][1] + dp[v][j][0] + 2 * w);
                f[idx & 1][i + j][1] = min(f[idx & 1][i + j][1], f[(idx & 1) ^ 1][i + j][1]);
            }
        }
        sz[u] += sz[v];
    }
    
    for(int i = 0; i <= k;i++){
        for(int j = 0; j <= 1;j++) dp[u][i][j] = min(f[0][i][j], f[1][i][j]);
    }
    dp[u][0][0] = 0, dp[u][1][0] = 0, dp[u][1][1] = 0, dp[u][0][1] = 0; 
}
void to_thic_cau(){
    cin >> n >> k >> x;
    for(int i = 1; i <= n - 1;i++){
        ll u,v,c; cin >> u >> v >> c;
        adj[u].pb({v, c}); adj[v].pb({u, c});
    }
    dfs(x, 0);
    cout << min(dp[x][k][0], dp[x][k][1]) << '\n';
}
 
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int idx = 0; idx < adj[u].size();idx++){
      |                      ~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 50516 KB Output is correct
2 Correct 136 ms 50516 KB Output is correct
3 Correct 230 ms 51020 KB Output is correct
4 Correct 166 ms 50696 KB Output is correct
5 Correct 141 ms 50596 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 50516 KB Output is correct
2 Correct 136 ms 50516 KB Output is correct
3 Correct 230 ms 51020 KB Output is correct
4 Correct 166 ms 50696 KB Output is correct
5 Correct 141 ms 50596 KB Output is correct
6 Correct 136 ms 50512 KB Output is correct
7 Correct 203 ms 50768 KB Output is correct
8 Correct 343 ms 50688 KB Output is correct
9 Correct 271 ms 50596 KB Output is correct
10 Correct 157 ms 50772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 135 ms 50516 KB Output is correct
7 Correct 136 ms 50516 KB Output is correct
8 Correct 230 ms 51020 KB Output is correct
9 Correct 166 ms 50696 KB Output is correct
10 Correct 141 ms 50596 KB Output is correct
11 Correct 136 ms 50512 KB Output is correct
12 Correct 203 ms 50768 KB Output is correct
13 Correct 343 ms 50688 KB Output is correct
14 Correct 271 ms 50596 KB Output is correct
15 Correct 157 ms 50772 KB Output is correct
16 Correct 173 ms 121028 KB Output is correct
17 Correct 338 ms 433488 KB Output is correct
18 Correct 216 ms 121168 KB Output is correct
19 Correct 336 ms 120928 KB Output is correct
20 Correct 188 ms 120916 KB Output is correct
21 Correct 613 ms 746320 KB Output is correct
22 Correct 574 ms 746000 KB Output is correct
23 Correct 696 ms 746064 KB Output is correct
24 Correct 558 ms 746068 KB Output is correct
25 Correct 652 ms 746324 KB Output is correct