oj.uz

Submission #729535

# Submission time Handle Problem Language Result Execution time Memory
729535 2023-04-24T08:47:30 Z thanhdanh436 Museum (CEOI17_museum) C++17
100 / 100
 485 ms 785228 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];
int f[N][N][2];

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);
    }

    memset(f, 0x3f, sizeof f);

    dfs(x, 0);

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 784096 KB Output is correct
2 Correct 288 ms 784040 KB Output is correct
3 Correct 292 ms 784140 KB Output is correct
4 Correct 283 ms 784144 KB Output is correct
5 Correct 291 ms 784076 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 784564 KB Output is correct
2 Correct 304 ms 784716 KB Output is correct
3 Correct 300 ms 785028 KB Output is correct
4 Correct 291 ms 784780 KB Output is correct
5 Correct 299 ms 784704 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 784564 KB Output is correct
2 Correct 304 ms 784716 KB Output is correct
3 Correct 300 ms 785028 KB Output is correct
4 Correct 291 ms 784780 KB Output is correct
5 Correct 299 ms 784704 KB Output is correct
6 Correct 301 ms 784656 KB Output is correct
7 Correct 325 ms 784900 KB Output is correct
8 Correct 302 ms 784616 KB Output is correct
9 Correct 283 ms 784608 KB Output is correct
10 Correct 287 ms 784664 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 784096 KB Output is correct
2 Correct 288 ms 784040 KB Output is correct
3 Correct 292 ms 784140 KB Output is correct
4 Correct 283 ms 784144 KB Output is correct
5 Correct 291 ms 784076 KB Output is correct
6 Correct 296 ms 784564 KB Output is correct
7 Correct 304 ms 784716 KB Output is correct
8 Correct 300 ms 785028 KB Output is correct
9 Correct 291 ms 784780 KB Output is correct
10 Correct 299 ms 784704 KB Output is correct
11 Correct 301 ms 784656 KB Output is correct
12 Correct 325 ms 784900 KB Output is correct
13 Correct 302 ms 784616 KB Output is correct
14 Correct 283 ms 784608 KB Output is correct
15 Correct 287 ms 784664 KB Output is correct
16 Correct 312 ms 784612 KB Output is correct
17 Correct 380 ms 784704 KB Output is correct
18 Correct 320 ms 784848 KB Output is correct
19 Correct 330 ms 784676 KB Output is correct
20 Correct 315 ms 784772 KB Output is correct
21 Correct 422 ms 784944 KB Output is correct
22 Correct 433 ms 784640 KB Output is correct
23 Correct 485 ms 784700 KB Output is correct
24 Correct 386 ms 784716 KB Output is correct
25 Correct 432 ms 785228 KB Output is correct