oj.uz

Submission #1105123

# Submission time Handle Problem Language Result Execution time Memory
1105123 2024-10-25T13:44:15 Z TrinhKhanhDung Museum (CEOI17_museum) C++14
100 / 100
 247 ms 278820 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e4 + 10;

int N, K, S;
vector<pair<int, int>> adj[MAX];
vector<ll> dp[MAX][2];
int cnt[MAX];

void dfs(int u, int p = -1){
    cnt[u] = 1;
    for(auto o: adj[u]){
        int v = o.fi;
        if(v == p) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }

    for(int i = 0; i < 2; i++){
        dp[u][i].resize(cnt[u] + 3, oo);
    }

    dp[u][1][1] = dp[u][0][1] = 0;

    int cur = 1;
    for(auto o: adj[u]){
        int v = o.fi;
        int c = o.se;
        if(v == p) continue;

        for(int i = cur; i >= 1; i--){
            for(int j = cnt[v]; j >= 1; j--){
                minimize(dp[u][0][i + j], dp[u][0][i] + dp[v][0][j] + 2 * c);
                minimize(dp[u][1][i + j], dp[u][1][i] + dp[v][0][j] + 2 * c);
                minimize(dp[u][1][i + j], dp[u][0][i] + dp[v][1][j] + c);
            }
        }

        cur += cnt[v];

        for(int i = 0; i < 2; i++){
            dp[v][i].clear();
        }
    }
}

void solve(){
    cin >> N >> K >> S;
    for(int i = 1; i < N; i++){
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    dfs(S);
    cout << dp[S][1][K] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//     freopen("btower.inp","r",stdin);
//     freopen("btower.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5704 KB Output is correct
2 Correct 83 ms 6432 KB Output is correct
3 Correct 239 ms 271236 KB Output is correct
4 Correct 141 ms 87624 KB Output is correct
5 Correct 94 ms 23504 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5704 KB Output is correct
2 Correct 83 ms 6432 KB Output is correct
3 Correct 239 ms 271236 KB Output is correct
4 Correct 141 ms 87624 KB Output is correct
5 Correct 94 ms 23504 KB Output is correct
6 Correct 92 ms 4424 KB Output is correct
7 Correct 187 ms 159304 KB Output is correct
8 Correct 107 ms 2892 KB Output is correct
9 Correct 91 ms 3144 KB Output is correct
10 Correct 81 ms 4312 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 1 ms 1172 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 81 ms 5704 KB Output is correct
7 Correct 83 ms 6432 KB Output is correct
8 Correct 239 ms 271236 KB Output is correct
9 Correct 141 ms 87624 KB Output is correct
10 Correct 94 ms 23504 KB Output is correct
11 Correct 92 ms 4424 KB Output is correct
12 Correct 187 ms 159304 KB Output is correct
13 Correct 107 ms 2892 KB Output is correct
14 Correct 91 ms 3144 KB Output is correct
15 Correct 81 ms 4312 KB Output is correct
16 Correct 86 ms 7140 KB Output is correct
17 Correct 80 ms 6480 KB Output is correct
18 Correct 141 ms 107336 KB Output is correct
19 Correct 94 ms 2888 KB Output is correct
20 Correct 77 ms 4424 KB Output is correct
21 Correct 188 ms 152904 KB Output is correct
22 Correct 80 ms 6080 KB Output is correct
23 Correct 90 ms 2888 KB Output is correct
24 Correct 76 ms 4168 KB Output is correct
25 Correct 247 ms 278820 KB Output is correct