oj.uz

Submission #938804

# Submission time Handle Problem Language Result Execution time Memory
938804 2024-03-05T14:46:41 Z Whisper Museum (CEOI17_museum) C++17
100 / 100
 491 ms 784976 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

//#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e4 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int numNode, staNode, K;
vector<pair<int, int>> G[MAX];

int dp[MAX][MAX][2];
int sz[MAX];
/*
    0. start a path at u go to u's subtree and end at u
    1. start a path at u go to u's subtree and end at a node in subtree
*/
void dfs(int u, int p = -1){
    sz[u] = 1;
    for (pair<int, int>& x : G[u]){
        int v = x.first, w = x.second;
        if(v ^ p){
            dfs(v, u);
            for (int k = sz[u]; k >= 0; --k){
                for (int l = sz[v]; l >= 0; --l){
                    minimize(dp[u][l + k][0], dp[v][l][0] + dp[u][k][0] + 2 * w);
                    minimize(dp[u][l + k][1], dp[v][l][0] + dp[u][k][1] + 2 * w);
                    minimize(dp[u][l + k][1], dp[v][l][1] + dp[u][k][0] + w);
                }
            }
            sz[u] += sz[v];
        }
    }
}
void Whisper(){
    cin >> numNode >> K >> staNode;
    for (int i = 1; i < numNode; ++i){
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    for (int i = 1; i <= numNode; ++i)
        for (int j = 2; j <= numNode; ++j)
            dp[i][j][0] = dp[i][j][1] = INF;
    dfs(staNode);

    cout << min(dp[staNode][K][1], dp[staNode][K][0]);
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 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 472 ms 784196 KB Output is correct
2 Correct 435 ms 784212 KB Output is correct
3 Correct 488 ms 784976 KB Output is correct
4 Correct 409 ms 784464 KB Output is correct
5 Correct 400 ms 784200 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 784196 KB Output is correct
2 Correct 435 ms 784212 KB Output is correct
3 Correct 488 ms 784976 KB Output is correct
4 Correct 409 ms 784464 KB Output is correct
5 Correct 400 ms 784200 KB Output is correct
6 Correct 392 ms 784524 KB Output is correct
7 Correct 427 ms 784420 KB Output is correct
8 Correct 491 ms 784212 KB Output is correct
9 Correct 470 ms 784252 KB Output is correct
10 Correct 404 ms 784536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 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 472 ms 784196 KB Output is correct
7 Correct 435 ms 784212 KB Output is correct
8 Correct 488 ms 784976 KB Output is correct
9 Correct 409 ms 784464 KB Output is correct
10 Correct 400 ms 784200 KB Output is correct
11 Correct 392 ms 784524 KB Output is correct
12 Correct 427 ms 784420 KB Output is correct
13 Correct 491 ms 784212 KB Output is correct
14 Correct 470 ms 784252 KB Output is correct
15 Correct 404 ms 784536 KB Output is correct
16 Correct 398 ms 784440 KB Output is correct
17 Correct 396 ms 784324 KB Output is correct
18 Correct 412 ms 784468 KB Output is correct
19 Correct 466 ms 784288 KB Output is correct
20 Correct 404 ms 784480 KB Output is correct
21 Correct 415 ms 784616 KB Output is correct
22 Correct 401 ms 784468 KB Output is correct
23 Correct 463 ms 784432 KB Output is correct
24 Correct 398 ms 784660 KB Output is correct
25 Correct 434 ms 784720 KB Output is correct