oj.uz

Submission #975316

# Submission time Handle Problem Language Result Execution time Memory
975316 2024-05-04T18:29:47 Z dosts Museum (CEOI17_museum) C++17
100 / 100
 601 ms 784476 KB 
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 1e4+1,inf = INT_MAX-2e6,MOD = 998244353;


int dp[N][2][N];
vector<pii> edges[N];
vi sz(N);

int szs(int node,int p) {
    sz[node] = 1;
    for (auto it : edges[node]) if (it.ff != p) sz[node]+=szs(it.ff,node);
    return sz[node];
}

void compute(int node,int p) {
    int curmx = 1;
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        int u = it.ff,w = it.ss;
        compute(u,node);
        curmx+=sz[u];
        for (int i=curmx;i>=2;i--) {
            for (int j=max(0,i-curmx+sz[u]);j<=min(i,sz[u]);j++) {
                dp[node][0][i] = min(dp[node][0][i],dp[node][0][i-j] + dp[u][1][j]+ 2*w);
                dp[node][0][i] = min(dp[node][0][i],dp[node][1][i-j] + dp[u][0][j] + w); 
                dp[node][1][i] = min(dp[node][1][i],dp[node][1][i-j] + dp[u][1][j]+ 2*w);
            }
        }
    }
}

void solve() {
    int n,k,x;
    cin >> n >> k >> x;
    for (int i=1;i<=n-1;i++) {
        int u,v,w;
        cin >> u >> v >> w;
        edges[u].push_back({v,w});
        edges[v].push_back({u,w});
    }
    for (int i=1;i<=n;i++) for(int j=0;j<2;j++) for (int k=2;k<=n;k++) dp[i][j][k] = inf;
    szs(x,x);
    compute(x,x);
    cout << dp[x][0][k] << endl;
}

                             
signed main() { 
    ios_base::sync_with_stdio(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 783952 KB Output is correct
2 Correct 413 ms 783952 KB Output is correct
3 Correct 475 ms 784476 KB Output is correct
4 Correct 440 ms 783956 KB Output is correct
5 Correct 443 ms 784036 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 783952 KB Output is correct
2 Correct 413 ms 783952 KB Output is correct
3 Correct 475 ms 784476 KB Output is correct
4 Correct 440 ms 783956 KB Output is correct
5 Correct 443 ms 784036 KB Output is correct
6 Correct 415 ms 784128 KB Output is correct
7 Correct 449 ms 784056 KB Output is correct
8 Correct 601 ms 784052 KB Output is correct
9 Correct 523 ms 784208 KB Output is correct
10 Correct 428 ms 784064 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 412 ms 783952 KB Output is correct
7 Correct 413 ms 783952 KB Output is correct
8 Correct 475 ms 784476 KB Output is correct
9 Correct 440 ms 783956 KB Output is correct
10 Correct 443 ms 784036 KB Output is correct
11 Correct 415 ms 784128 KB Output is correct
12 Correct 449 ms 784056 KB Output is correct
13 Correct 601 ms 784052 KB Output is correct
14 Correct 523 ms 784208 KB Output is correct
15 Correct 428 ms 784064 KB Output is correct
16 Correct 415 ms 783972 KB Output is correct
17 Correct 417 ms 783964 KB Output is correct
18 Correct 438 ms 784424 KB Output is correct
19 Correct 542 ms 784212 KB Output is correct
20 Correct 421 ms 784056 KB Output is correct
21 Correct 461 ms 784348 KB Output is correct
22 Correct 412 ms 783952 KB Output is correct
23 Correct 533 ms 783952 KB Output is correct
24 Correct 415 ms 783952 KB Output is correct
25 Correct 479 ms 784476 KB Output is correct