oj.uz

Submission #952152

# Submission time Handle Problem Language Result Execution time Memory
952152 2024-03-23T06:55:47 Z vjudge1 Museum (CEOI17_museum) C++14
100 / 100
 518 ms 755796 KB 
#include<bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int MAXN = 1e4 + 5;
int f[MAXN][MAXN][2], k, siz[MAXN];
vector<pii> edge[MAXN];
void dfs(int i, int fa){
	siz[i] = 1;
	f[i][0][0] = f[i][1][0] = f[i][0][1] = f[i][1][1] = 0;
	for(pii v : edge[i]){
		if(v.F == fa) continue;
		dfs(v.F, i);
		for(int p = min(k, siz[i]); p >= 1; p--){
			for(int x = 0; x <= min(k, siz[v.F]); x++){
				f[i][p + x][0] = min(f[i][p + x][0], f[i][p][0] + f[v.F][x][0] + 2 * v.S);
				f[i][p + x][1] = min(f[i][p + x][1], f[i][p][0] + f[v.F][x][1] + v.S);
				f[i][p + x][1] = min(f[i][p + x][1], f[i][p][1] + f[v.F][x][0] + 2 * v.S);
			}
		}
		siz[i] += siz[v.F];
	}
}
int main(){
	int n, x, u, v, c;
	scanf("%d%d%d", &n, &k, &x);
	for(int i = 1; i < n; i++){
		scanf("%d%d%d", &u, &v, &c);
		edge[u].push_back(mp(v, c));
		edge[v].push_back(mp(u, c));
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= k; j++)
			f[i][j][1] = f[i][j][0] = 1e9;
	dfs(x, 0);
	printf("%d", f[x][k][1]);
	return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 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 94 ms 227152 KB Output is correct
2 Correct 47 ms 227320 KB Output is correct
3 Correct 42 ms 227552 KB Output is correct
4 Correct 42 ms 227164 KB Output is correct
5 Correct 42 ms 227152 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 227152 KB Output is correct
2 Correct 47 ms 227320 KB Output is correct
3 Correct 42 ms 227552 KB Output is correct
4 Correct 42 ms 227164 KB Output is correct
5 Correct 42 ms 227152 KB Output is correct
6 Correct 41 ms 227156 KB Output is correct
7 Correct 44 ms 231248 KB Output is correct
8 Correct 48 ms 223556 KB Output is correct
9 Correct 47 ms 227108 KB Output is correct
10 Correct 43 ms 229212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 94 ms 227152 KB Output is correct
7 Correct 47 ms 227320 KB Output is correct
8 Correct 42 ms 227552 KB Output is correct
9 Correct 42 ms 227164 KB Output is correct
10 Correct 42 ms 227152 KB Output is correct
11 Correct 41 ms 227156 KB Output is correct
12 Correct 44 ms 231248 KB Output is correct
13 Correct 48 ms 223556 KB Output is correct
14 Correct 47 ms 227108 KB Output is correct
15 Correct 43 ms 229212 KB Output is correct
16 Correct 91 ms 285900 KB Output is correct
17 Correct 275 ms 519768 KB Output is correct
18 Correct 91 ms 284244 KB Output is correct
19 Correct 122 ms 284096 KB Output is correct
20 Correct 91 ms 283984 KB Output is correct
21 Correct 415 ms 755796 KB Output is correct
22 Correct 355 ms 755284 KB Output is correct
23 Correct 518 ms 755280 KB Output is correct
24 Correct 369 ms 755432 KB Output is correct
25 Correct 377 ms 755640 KB Output is correct