oj.uz

Submission #1098565

# Submission time Handle Problem Language Result Execution time Memory
1098565 2024-10-09T15:33:55 Z coldbr3w Museum (CEOI17_museum) C++17
100 / 100
 704 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 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 704 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 139 ms 50512 KB Output is correct
2 Correct 135 ms 50516 KB Output is correct
3 Correct 228 ms 51024 KB Output is correct
4 Correct 168 ms 50516 KB Output is correct
5 Correct 146 ms 50516 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 50512 KB Output is correct
2 Correct 135 ms 50516 KB Output is correct
3 Correct 228 ms 51024 KB Output is correct
4 Correct 168 ms 50516 KB Output is correct
5 Correct 146 ms 50516 KB Output is correct
6 Correct 142 ms 50512 KB Output is correct
7 Correct 212 ms 50768 KB Output is correct
8 Correct 355 ms 50524 KB Output is correct
9 Correct 266 ms 50564 KB Output is correct
10 Correct 154 ms 50768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 704 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 139 ms 50512 KB Output is correct
7 Correct 135 ms 50516 KB Output is correct
8 Correct 228 ms 51024 KB Output is correct
9 Correct 168 ms 50516 KB Output is correct
10 Correct 146 ms 50516 KB Output is correct
11 Correct 142 ms 50512 KB Output is correct
12 Correct 212 ms 50768 KB Output is correct
13 Correct 355 ms 50524 KB Output is correct
14 Correct 266 ms 50564 KB Output is correct
15 Correct 154 ms 50768 KB Output is correct
16 Correct 176 ms 120920 KB Output is correct
17 Correct 351 ms 433492 KB Output is correct
18 Correct 215 ms 121076 KB Output is correct
19 Correct 341 ms 120916 KB Output is correct
20 Correct 189 ms 120916 KB Output is correct
21 Correct 622 ms 746304 KB Output is correct
22 Correct 552 ms 746064 KB Output is correct
23 Correct 704 ms 745892 KB Output is correct
24 Correct 529 ms 746064 KB Output is correct
25 Correct 587 ms 746324 KB Output is correct