oj.uz

Submission #252048

# Submission time Handle Problem Language Result Execution time Memory
252048 2020-07-23T23:36:57 Z aZvezda Museum (CEOI17_museum) C++14
100 / 100
 806 ms 785272 KB 
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 1e4 + 10;
unsigned int dp1[MAX_N][MAX_N];
unsigned int dp2[MAX_N][MAX_N];
int sz[MAX_N];
vector<pair<int, unsigned int> > g[MAX_N];

void dfs(int x, int p) {
    sz[x] = 1;
    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        dfs(it.first, x);
    }
    dp1[x][1] = 0;
    dp2[x][1] = 0;
    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        for(int i = sz[x]; i >= 0; i --) {
            for(int j = min(MAX_N, sz[it.first]); j >= 0; j --) {
                chkmin(dp1[x][i + j], dp1[x][i] + dp1[it.first][j] + 2ll * it.second);
                chkmin(dp2[x][i + j], dp2[x][i] + dp1[it.first][j] + 2ll * it.second);
                chkmin(dp2[x][i + j], dp1[x][i] + dp2[it.first][j] + it.second);
                chkmin(dp2[x][i + j], dp1[x][i] + dp1[it.first][j] + it.second);
            }
        }
        sz[x] += sz[it.first];
    }
    return;
    cout << "Dfs " << x << endl;
    for(int i = 0; i <= sz[x]; i ++) {
        cout << dp1[x][i] << " ";
    }
    cout << endl;
    for(int i = 0; i <= sz[x]; i ++) {
        cout << dp2[x][i] << " ";
    }
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, k, x;
    cin >> n >> k >> x;
    for(int i = 0; i < n - 1; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 0; i <= n; i ++) {
        for(int j = 0; j <= n; j ++) {
            dp1[i][j] = 2 * mod;
            dp2[i][j] = 2 * mod;
        }
    }
    dfs(x, 0);
    cout << dp2[x][k] << endl;
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 784640 KB Output is correct
2 Correct 607 ms 784584 KB Output is correct
3 Correct 689 ms 785016 KB Output is correct
4 Correct 643 ms 784760 KB Output is correct
5 Correct 651 ms 784760 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 784640 KB Output is correct
2 Correct 607 ms 784584 KB Output is correct
3 Correct 689 ms 785016 KB Output is correct
4 Correct 643 ms 784760 KB Output is correct
5 Correct 651 ms 784760 KB Output is correct
6 Correct 605 ms 784812 KB Output is correct
7 Correct 639 ms 784952 KB Output is correct
8 Correct 806 ms 784632 KB Output is correct
9 Correct 729 ms 784696 KB Output is correct
10 Correct 604 ms 784700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 623 ms 784640 KB Output is correct
7 Correct 607 ms 784584 KB Output is correct
8 Correct 689 ms 785016 KB Output is correct
9 Correct 643 ms 784760 KB Output is correct
10 Correct 651 ms 784760 KB Output is correct
11 Correct 605 ms 784812 KB Output is correct
12 Correct 639 ms 784952 KB Output is correct
13 Correct 806 ms 784632 KB Output is correct
14 Correct 729 ms 784696 KB Output is correct
15 Correct 604 ms 784700 KB Output is correct
16 Correct 583 ms 784816 KB Output is correct
17 Correct 604 ms 784760 KB Output is correct
18 Correct 643 ms 784888 KB Output is correct
19 Correct 763 ms 784632 KB Output is correct
20 Correct 597 ms 784760 KB Output is correct
21 Correct 635 ms 785016 KB Output is correct
22 Correct 600 ms 785016 KB Output is correct
23 Correct 731 ms 784888 KB Output is correct
24 Correct 623 ms 784888 KB Output is correct
25 Correct 681 ms 785272 KB Output is correct