oj.uz

Submission #156343

# Submission time Handle Problem Language Result Execution time Memory
156343 2019-10-05T09:12:05 Z farmerboy Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 433500 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) 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) {
                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 80 ms 45328 KB Output is correct
2 Correct 79 ms 45688 KB Output is correct
3 Correct 204 ms 214120 KB Output is correct
4 Correct 93 ms 97528 KB Output is correct
5 Correct 62 ms 56312 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 45328 KB Output is correct
2 Correct 79 ms 45688 KB Output is correct
3 Correct 204 ms 214120 KB Output is correct
4 Correct 93 ms 97528 KB Output is correct
5 Correct 62 ms 56312 KB Output is correct
6 Correct 96 ms 45980 KB Output is correct
7 Correct 137 ms 147708 KB Output is correct
8 Correct 519 ms 433500 KB Output is correct
9 Correct 274 ms 198860 KB Output is correct
10 Correct 134 ms 85496 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 80 ms 45328 KB Output is correct
7 Correct 79 ms 45688 KB Output is correct
8 Correct 204 ms 214120 KB Output is correct
9 Correct 93 ms 97528 KB Output is correct
10 Correct 62 ms 56312 KB Output is correct
11 Correct 96 ms 45980 KB Output is correct
12 Correct 137 ms 147708 KB Output is correct
13 Correct 519 ms 433500 KB Output is correct
14 Correct 274 ms 198860 KB Output is correct
15 Correct 134 ms 85496 KB Output is correct
16 Correct 493 ms 46348 KB Output is correct
17 Execution timed out 3084 ms 45944 KB Time limit exceeded
18 Halted 0 ms 0 KB -