oj.uz

Submission #952004

# Submission time Handle Problem Language Result Execution time Memory
952004 2024-03-23T03:37:21 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 757328 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, k, x;
int dp[N][N][2];
int son[N];
vector<pair<int, int>> G[N];
void dfs(int fa, int u){
	son[u] = 1;
	dp[u][0][0] = dp[u][1][0] = dp[u][1][1] = dp[u][0][1] = 0;
	for(auto e : G[u]){
		int v = e.first;
		int w = e.second;
		if(v == fa) continue;
		dfs(u, v);
		son[u] += son[v];
		for(int i = min(son[u], k); i >= 0; i--){
			for(int j = 0; j <= min(i, son[v]); j++){
				dp[u][i][0] = min(dp[u][i - j][0] + dp[v][j][0] + 2 * w, dp[u][i][0]);
				dp[u][i][1] = min(dp[u][i - j][1] + dp[v][j][0] + w * 2, dp[u][i][1]);
				dp[u][i][1] = min(dp[u][i - j][0] + dp[v][j][1] + w, dp[u][i][1]);
			}
		}
	}
}
int main(){
//	freopen("museum.in","r", stdin);
//	freopen("museum.out","w", stdout);
	scanf("%d %d %d", &n, &k, &x);
	for(int i = 1; i < n; i++){
		int x, y ,z;
		scanf("%d %d %d", &x, &y, &z);
		G[x].push_back({y, z});
		G[y].push_back({x, z});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			dp[i][j][1] = dp[i][j][0] = 1e9;	
		}
	}
	dfs(0, x);
	printf("%d", dp[x][k][1]);
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d %d %d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 265560 KB Output is correct
2 Correct 48 ms 269396 KB Output is correct
3 Correct 86 ms 271860 KB Output is correct
4 Correct 66 ms 269512 KB Output is correct
5 Correct 60 ms 269388 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 265560 KB Output is correct
2 Correct 48 ms 269396 KB Output is correct
3 Correct 86 ms 271860 KB Output is correct
4 Correct 66 ms 269512 KB Output is correct
5 Correct 60 ms 269388 KB Output is correct
6 Correct 46 ms 269396 KB Output is correct
7 Correct 82 ms 271496 KB Output is correct
8 Correct 48 ms 271440 KB Output is correct
9 Correct 48 ms 269396 KB Output is correct
10 Correct 47 ms 271432 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 49 ms 265560 KB Output is correct
7 Correct 48 ms 269396 KB Output is correct
8 Correct 86 ms 271860 KB Output is correct
9 Correct 66 ms 269512 KB Output is correct
10 Correct 60 ms 269388 KB Output is correct
11 Correct 46 ms 269396 KB Output is correct
12 Correct 82 ms 271496 KB Output is correct
13 Correct 48 ms 271440 KB Output is correct
14 Correct 48 ms 269396 KB Output is correct
15 Correct 47 ms 271432 KB Output is correct
16 Correct 151 ms 320600 KB Output is correct
17 Correct 702 ms 539296 KB Output is correct
18 Correct 1869 ms 318972 KB Output is correct
19 Correct 116 ms 318800 KB Output is correct
20 Correct 110 ms 320440 KB Output is correct
21 Execution timed out 3097 ms 757328 KB Time limit exceeded
22 Halted 0 ms 0 KB -