oj.uz

Submission #252043

# Submission time Handle Problem Language Result Execution time Memory
252043 2020-07-23T23:18:47 Z aZvezda Museum (CEOI17_museum) C++14
80 / 100
 1274 ms 785144 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]) {
        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);
            }
        }
        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 884 ms 784844 KB Output is correct
2 Correct 891 ms 784760 KB Output is correct
3 Correct 1036 ms 785144 KB Output is correct
4 Correct 941 ms 784888 KB Output is correct
5 Correct 918 ms 784760 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 884 ms 784844 KB Output is correct
2 Correct 891 ms 784760 KB Output is correct
3 Correct 1036 ms 785144 KB Output is correct
4 Correct 941 ms 784888 KB Output is correct
5 Correct 918 ms 784760 KB Output is correct
6 Correct 829 ms 784888 KB Output is correct
7 Correct 970 ms 785016 KB Output is correct
8 Correct 1274 ms 784760 KB Output is correct
9 Correct 1127 ms 784760 KB Output is correct
10 Correct 827 ms 784736 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 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 884 ms 784844 KB Output is correct
7 Correct 891 ms 784760 KB Output is correct
8 Correct 1036 ms 785144 KB Output is correct
9 Correct 941 ms 784888 KB Output is correct
10 Correct 918 ms 784760 KB Output is correct
11 Correct 829 ms 784888 KB Output is correct
12 Correct 970 ms 785016 KB Output is correct
13 Correct 1274 ms 784760 KB Output is correct
14 Correct 1127 ms 784760 KB Output is correct
15 Correct 827 ms 784736 KB Output is correct
16 Correct 846 ms 784836 KB Output is correct
17 Correct 810 ms 784888 KB Output is correct
18 Correct 905 ms 784888 KB Output is correct
19 Correct 1109 ms 784840 KB Output is correct
20 Correct 923 ms 784632 KB Output is correct
21 Incorrect 996 ms 785004 KB Output isn't correct
22 Halted 0 ms 0 KB -