oj.uz

Submission #729529

# Submission time Handle Problem Language Result Execution time Memory
729529 2023-04-24T08:44:42 Z thanhdanh436 Museum (CEOI17_museum) C++17
80 / 100
 814 ms 1048576 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file ""
using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e4 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1

template<class X, class Y> bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
template<class X, class Y> bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

int n, k, x;
vector<pair<int, int> > adj[N];
int sz[N];
vector<vector<vector<int> > > f;

void dfs(int u, int p) {
	sz[u] = 1;
	f[u][1][0] = f[u][1][1] = 0;

	for (auto [v, c] : adj[u]) if (v != p) {
		dfs(v, u);
		for (int i = min(k, sz[u]); i >= 0; --i)
			for (int j = min(k, sz[v]); j >= 0; --j) if (i + j <= k) {
				minimize(f[u][i + j][0], f[u][i][0] + f[v][j][0] + c * 2);
				minimize(f[u][i + j][1], f[u][i][1] + f[v][j][0] + c * 2);
				minimize(f[u][i + j][1], f[u][i][0] + f[v][j][1] + c);
			}
		sz[u] += sz[v];
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r",stdin);
    // freopen(file".out", "w",stdout);

    cin >> n >> k >> x;
    for (int i = 1; i < n; ++i) {
    	int u, v, c;
    	cin >> u >> v >> c;
    	adj[u].emplace_back(v, c);
    	adj[v].emplace_back(u, c);
    }

    f.resize(n + 5, vector<vector<int> > (k + 5, vector<int> (2, 1e9)));

    dfs(x, 0);

    cout << f[x][k][1];
    
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 58984 KB Output is correct
2 Correct 71 ms 58940 KB Output is correct
3 Correct 77 ms 59208 KB Output is correct
4 Correct 89 ms 58592 KB Output is correct
5 Correct 73 ms 58444 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 58984 KB Output is correct
2 Correct 71 ms 58940 KB Output is correct
3 Correct 77 ms 59208 KB Output is correct
4 Correct 89 ms 58592 KB Output is correct
5 Correct 73 ms 58444 KB Output is correct
6 Correct 70 ms 58992 KB Output is correct
7 Correct 76 ms 59180 KB Output is correct
8 Correct 68 ms 58936 KB Output is correct
9 Correct 77 ms 58896 KB Output is correct
10 Correct 68 ms 58952 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 564 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 82 ms 58984 KB Output is correct
7 Correct 71 ms 58940 KB Output is correct
8 Correct 77 ms 59208 KB Output is correct
9 Correct 89 ms 58592 KB Output is correct
10 Correct 73 ms 58444 KB Output is correct
11 Correct 70 ms 58992 KB Output is correct
12 Correct 76 ms 59180 KB Output is correct
13 Correct 68 ms 58936 KB Output is correct
14 Correct 77 ms 58896 KB Output is correct
15 Correct 68 ms 58952 KB Output is correct
16 Correct 564 ms 552560 KB Output is correct
17 Runtime error 814 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -