oj.uz

Submission #252044

# Submission time Handle Problem Language Result Execution time Memory
252044 2020-07-23T23:22:24 Z aZvezda Museum (CEOI17_museum) C++14
80 / 100
 1466 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);
                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 842 ms 784756 KB Output is correct
2 Correct 874 ms 784632 KB Output is correct
3 Correct 1008 ms 785116 KB Output is correct
4 Correct 972 ms 784872 KB Output is correct
5 Correct 1039 ms 784632 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 784756 KB Output is correct
2 Correct 874 ms 784632 KB Output is correct
3 Correct 1008 ms 785116 KB Output is correct
4 Correct 972 ms 784872 KB Output is correct
5 Correct 1039 ms 784632 KB Output is correct
6 Correct 911 ms 784720 KB Output is correct
7 Correct 947 ms 785144 KB Output is correct
8 Correct 1466 ms 784632 KB Output is correct
9 Correct 1259 ms 784632 KB Output is correct
10 Correct 925 ms 784880 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 842 ms 784756 KB Output is correct
7 Correct 874 ms 784632 KB Output is correct
8 Correct 1008 ms 785116 KB Output is correct
9 Correct 972 ms 784872 KB Output is correct
10 Correct 1039 ms 784632 KB Output is correct
11 Correct 911 ms 784720 KB Output is correct
12 Correct 947 ms 785144 KB Output is correct
13 Correct 1466 ms 784632 KB Output is correct
14 Correct 1259 ms 784632 KB Output is correct
15 Correct 925 ms 784880 KB Output is correct
16 Correct 849 ms 784812 KB Output is correct
17 Correct 846 ms 784760 KB Output is correct
18 Correct 927 ms 784760 KB Output is correct
19 Correct 1244 ms 784760 KB Output is correct
20 Correct 818 ms 784740 KB Output is correct
21 Incorrect 922 ms 785016 KB Output isn't correct
22 Halted 0 ms 0 KB -