oj.uz

Submission #156486

# Submission time Handle Problem Language Result Execution time Memory
156486 2019-10-06T07:30:24 Z lyc Museum (CEOI17_museum) C++14
20 / 100
 3000 ms 44488 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 10005;
int N, K, X, A, B, C;
vector<ii> al[MX_N];
int f[MX_N][MX_N][2], g[MX_N];

void dfs(int u, int p) {
    g[u] = 1;
    f[u][1][0] = f[u][1][1] = 0;
    for (auto v : al[u]) if (v.fi != p) {
        dfs(v.fi,u);
        FOR(j,1,g[v.fi]) f[u][g[u]+j][0] = f[u][g[u]+j][1] = 1e9;
        g[u] += g[v.fi];

        RFOR(j,g[u],2) FOR(k,1,g[v.fi]){
            f[u][j][0] = min(f[u][j][0], f[u][j-k][0] + f[v.fi][k][0] + 2*v.sc);
            f[u][j][1] = min(f[u][j][1], f[u][j-k][0] + f[v.fi][k][1] + v.sc);
            f[u][j][1] = min(f[u][j][1], f[u][j-k][1] + f[v.fi][k][0] + 2*v.sc);
        }
    }
    //printf("%d (%d):\n", u, g[u]);
    //FOR(j,0,g[u]) printf("%d ", f[u][j][0]);
    //printf("\n");
    //FOR(j,0,g[u]) printf("%d ", f[u][j][1]);
    //printf("\n");
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K >> X;
    FOR(i,1,N-1){ cin >> A >> B >> C; al[A].emplace_back(B,C); al[B].emplace_back(A,C); }
    dfs(X,0);
    cout << f[X][K][1] << '\n';
}

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 620 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 632 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2224 ms 44244 KB Output is correct
2 Execution timed out 3103 ms 44488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2224 ms 44244 KB Output is correct
2 Execution timed out 3103 ms 44488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

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 620 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2224 ms 44244 KB Output is correct
7 Execution timed out 3103 ms 44488 KB Time limit exceeded
8 Halted 0 ms 0 KB -