oj.uz

Submission #252042

# Submission time Handle Problem Language Result Execution time Memory
252042 2020-07-23T23:17:38 Z aZvezda Museum (CEOI17_museum) C++14
80 / 100
 1258 ms 785240 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;
int dp1[MAX_N][MAX_N];
int dp2[MAX_N][MAX_N];
int sz[MAX_N];
vector<pair<int, 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]) {
        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] + 2 * it.second);
                chkmin(dp2[x][i + j], dp2[x][i] + dp1[it.first][j] + 2 * it.second);
                chkmin(dp2[x][i + j], dp1[x][i] + dp2[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] = mod;
            dp2[i][j] = 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 896 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 1036 ms 784760 KB Output is correct
2 Correct 867 ms 784768 KB Output is correct
3 Correct 1008 ms 785240 KB Output is correct
4 Correct 882 ms 784888 KB Output is correct
5 Correct 885 ms 784888 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 784760 KB Output is correct
2 Correct 867 ms 784768 KB Output is correct
3 Correct 1008 ms 785240 KB Output is correct
4 Correct 882 ms 784888 KB Output is correct
5 Correct 885 ms 784888 KB Output is correct
6 Correct 860 ms 784888 KB Output is correct
7 Correct 928 ms 785144 KB Output is correct
8 Correct 1258 ms 784808 KB Output is correct
9 Correct 1048 ms 784952 KB Output is correct
10 Correct 833 ms 784840 KB Output is correct

Subtask #4
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 896 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1036 ms 784760 KB Output is correct
7 Correct 867 ms 784768 KB Output is correct
8 Correct 1008 ms 785240 KB Output is correct
9 Correct 882 ms 784888 KB Output is correct
10 Correct 885 ms 784888 KB Output is correct
11 Correct 860 ms 784888 KB Output is correct
12 Correct 928 ms 785144 KB Output is correct
13 Correct 1258 ms 784808 KB Output is correct
14 Correct 1048 ms 784952 KB Output is correct
15 Correct 833 ms 784840 KB Output is correct
16 Correct 783 ms 784748 KB Output is correct
17 Correct 806 ms 784868 KB Output is correct
18 Correct 903 ms 785168 KB Output is correct
19 Correct 1140 ms 784852 KB Output is correct
20 Correct 816 ms 784804 KB Output is correct
21 Incorrect 897 ms 785144 KB Output isn't correct
22 Halted 0 ms 0 KB -