oj.uz

Submission #156345

# Submission time Handle Problem Language Result Execution time Memory
156345 2019-10-05T09:27:07 Z farmerboy Museum (CEOI17_museum) C++14
100 / 100
 1384 ms 433308 KB 
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 10010;
const int MAXM = 1010;
const int MAXK = 110;
const int MAXQ = 200010;

int n, k, leftChild[MAXN], sibling[MAXN], num[MAXN], num2[MAXN];
int dp[MAXN][MAXN][2];
II par[MAXN];
vector<II> a[MAXN];

// reconstruct the tree
void dfs(int u, int p) {
    num[u] = 1;
    int pre = -1;
    FOR(i,0,SZ(a[u])-1) {
        int v = a[u][i].FI;
        int c = a[u][i].SE;
        if (v != p) {
            if (pre == -1) leftChild[u] = v;
            else sibling[pre] = v;
            pre = v;
            par[v] = II(u, c);
            dfs(v, u);
            num[u] += num[v];
        } 
    }
}

void dfs2(int u) {
    num2[u] = 1;
    if (leftChild[u] != -1) {
        dfs2(leftChild[u]);
        num2[u] += num2[leftChild[u]];
    }
    if (sibling[u] != -1) {
        dfs2(sibling[u]);
        num2[u] += num2[sibling[u]];
    }
    dp[u][0][0] = dp[u][0][1] = 0;
    FOR(i,1,num2[u]) dp[u][i][0] = dp[u][i][1] = -1;
}

int solve(int u, int K, int p) {
    if (num2[u] < K) return 1000000000;
    if (dp[u][K][p] != -1) return dp[u][K][p];

    int res = 1000000000;
    int l = leftChild[u], s = sibling[u];
    int e = par[u].SE;

    if (l == -1 && s == -1) {
        if (p == 0) res = 2 * e;
        else res = e;
    }

    if (l != -1 && s == -1) {
        if (p == 0) res = min(res, solve(l, K-1, 0) + 2 * e);
        else res = min(res, solve(l, K-1, 1) + e);
    }

    if (l == -1 && s != -1) {
        if (p == 0) res = min(res, min(solve(s, K, 0), solve(s, K-1, 0) + 2 * e));
        else res = min(res, min(solve(s, K, 1), min(solve(s, K-1, 0) + e, solve(s, K-1, 1) + 2*e)));
    }

    if (l != -1 && s != -1) {
        int L = max(0, K-1-num2[s]), R = min(K-1, num2[l]);
        if (p == 0) {
            res = min(res, solve(s, K, 0));
            FOR(i,L,R) res = min(res, solve(l, i, 0) + solve(s, K-i-1, 0) + 2*e);
        }
        else {
            res = min(res, solve(s, K, 1));
            FOR(i,L,R) {
                res = min(res, solve(l, i, 1) + solve(s, K-i-1, 0) + e);
                res = min(res, solve(l, i, 0) + solve(s, K-i-1, 1) + 2*e);
            }
        }
    }

    return dp[u][K][p] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int x;
    cin >> n >> k >> x;
    FOR(i,1,n) leftChild[i] = sibling[i] = -1;
    FOR(i,1,n-1) {
        int u, v, c;
        cin >> u >> v >> c;
        a[u].emplace_back(II(v, c));
        a[v].emplace_back(II(u, c));
    }
    dfs(x, 0);
    dfs2(x);

    cout << solve(x, k, 1);
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 45132 KB Output is correct
2 Correct 66 ms 45460 KB Output is correct
3 Correct 192 ms 213972 KB Output is correct
4 Correct 92 ms 97412 KB Output is correct
5 Correct 57 ms 56252 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 45132 KB Output is correct
2 Correct 66 ms 45460 KB Output is correct
3 Correct 192 ms 213972 KB Output is correct
4 Correct 92 ms 97412 KB Output is correct
5 Correct 57 ms 56252 KB Output is correct
6 Correct 70 ms 45852 KB Output is correct
7 Correct 132 ms 147432 KB Output is correct
8 Correct 497 ms 433308 KB Output is correct
9 Correct 279 ms 198648 KB Output is correct
10 Correct 132 ms 85408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 67 ms 45132 KB Output is correct
7 Correct 66 ms 45460 KB Output is correct
8 Correct 192 ms 213972 KB Output is correct
9 Correct 92 ms 97412 KB Output is correct
10 Correct 57 ms 56252 KB Output is correct
11 Correct 70 ms 45852 KB Output is correct
12 Correct 132 ms 147432 KB Output is correct
13 Correct 497 ms 433308 KB Output is correct
14 Correct 279 ms 198648 KB Output is correct
15 Correct 132 ms 85408 KB Output is correct
16 Correct 208 ms 46248 KB Output is correct
17 Correct 476 ms 45816 KB Output is correct
18 Correct 270 ms 110328 KB Output is correct
19 Correct 1384 ms 346788 KB Output is correct
20 Correct 254 ms 61688 KB Output is correct
21 Correct 775 ms 138856 KB Output is correct
22 Correct 223 ms 45816 KB Output is correct
23 Correct 1000 ms 347836 KB Output is correct
24 Correct 277 ms 57464 KB Output is correct
25 Correct 1094 ms 213752 KB Output is correct