oj.uz

Submission #873897

# Submission time Handle Problem Language Result Execution time Memory
873897 2023-11-16T02:35:38 Z noiaint Museum (CEOI17_museum) C++17
100 / 100
 371 ms 785308 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 321 ms 784224 KB Output is correct
2 Correct 279 ms 784196 KB Output is correct
3 Correct 266 ms 784208 KB Output is correct
4 Correct 230 ms 784124 KB Output is correct
5 Correct 224 ms 784216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 784684 KB Output is correct
2 Correct 226 ms 784748 KB Output is correct
3 Correct 210 ms 785080 KB Output is correct
4 Correct 212 ms 784852 KB Output is correct
5 Correct 207 ms 784728 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 784684 KB Output is correct
2 Correct 226 ms 784748 KB Output is correct
3 Correct 210 ms 785080 KB Output is correct
4 Correct 212 ms 784852 KB Output is correct
5 Correct 207 ms 784728 KB Output is correct
6 Correct 209 ms 784728 KB Output is correct
7 Correct 202 ms 785064 KB Output is correct
8 Correct 202 ms 784724 KB Output is correct
9 Correct 203 ms 784940 KB Output is correct
10 Correct 206 ms 784772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 784224 KB Output is correct
2 Correct 279 ms 784196 KB Output is correct
3 Correct 266 ms 784208 KB Output is correct
4 Correct 230 ms 784124 KB Output is correct
5 Correct 224 ms 784216 KB Output is correct
6 Correct 222 ms 784684 KB Output is correct
7 Correct 226 ms 784748 KB Output is correct
8 Correct 210 ms 785080 KB Output is correct
9 Correct 212 ms 784852 KB Output is correct
10 Correct 207 ms 784728 KB Output is correct
11 Correct 209 ms 784728 KB Output is correct
12 Correct 202 ms 785064 KB Output is correct
13 Correct 202 ms 784724 KB Output is correct
14 Correct 203 ms 784940 KB Output is correct
15 Correct 206 ms 784772 KB Output is correct
16 Correct 221 ms 784728 KB Output is correct
17 Correct 267 ms 784724 KB Output is correct
18 Correct 238 ms 784952 KB Output is correct
19 Correct 245 ms 784980 KB Output is correct
20 Correct 221 ms 784580 KB Output is correct
21 Correct 320 ms 784932 KB Output is correct
22 Correct 320 ms 784580 KB Output is correct
23 Correct 371 ms 784720 KB Output is correct
24 Correct 337 ms 784668 KB Output is correct
25 Correct 364 ms 785308 KB Output is correct