oj.uz

Submission #156344

# Submission time Handle Problem Language Result Execution time Memory
156344 2019-10-05T09:18:19 Z farmerboy Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 433656 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) {
        if (p == 0) {
            res = min(res, solve(s, K, 0));
            FOR(i,0,K-1) {
                if (num2[l] < i || num2[s] < K-i-1) continue;
                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,0,K-1) {
                if (num2[l] < i || num2[s] < K-i-1) continue;
                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 2 ms 632 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 74 ms 45304 KB Output is correct
2 Correct 72 ms 45564 KB Output is correct
3 Correct 190 ms 214084 KB Output is correct
4 Correct 108 ms 97528 KB Output is correct
5 Correct 70 ms 56312 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 45304 KB Output is correct
2 Correct 72 ms 45564 KB Output is correct
3 Correct 190 ms 214084 KB Output is correct
4 Correct 108 ms 97528 KB Output is correct
5 Correct 70 ms 56312 KB Output is correct
6 Correct 78 ms 45980 KB Output is correct
7 Correct 134 ms 147548 KB Output is correct
8 Correct 506 ms 433656 KB Output is correct
9 Correct 290 ms 198792 KB Output is correct
10 Correct 136 ms 85476 KB Output is correct

Subtask #4
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 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 74 ms 45304 KB Output is correct
7 Correct 72 ms 45564 KB Output is correct
8 Correct 190 ms 214084 KB Output is correct
9 Correct 108 ms 97528 KB Output is correct
10 Correct 70 ms 56312 KB Output is correct
11 Correct 78 ms 45980 KB Output is correct
12 Correct 134 ms 147548 KB Output is correct
13 Correct 506 ms 433656 KB Output is correct
14 Correct 290 ms 198792 KB Output is correct
15 Correct 136 ms 85476 KB Output is correct
16 Correct 264 ms 46248 KB Output is correct
17 Correct 714 ms 45816 KB Output is correct
18 Correct 525 ms 110628 KB Output is correct
19 Correct 1358 ms 346980 KB Output is correct
20 Correct 323 ms 62072 KB Output is correct
21 Execution timed out 3036 ms 138980 KB Time limit exceeded
22 Halted 0 ms 0 KB -