oj.uz

Submission #952011

# Submission time Handle Problem Language Result Execution time Memory
952011 2024-03-23T03:39:48 Z vjudge1 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 756924 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);
		siz[i] += siz[v.F];
		for(int p = min(k, siz[i]); p >= 1; p--){
			for(int x = 0; x <= min(p, siz[v.F]); x++){
				f[i][p][0] = min(f[i][p][0], f[i][p - x][0] + f[v.F][x][0] + 2 * v.S);
				f[i][p][1] = min(f[i][p][1], f[i][p - x][0] + f[v.F][x][1] + v.S);
				f[i][p][1] = min(f[i][p][1], f[i][p - x][1] + f[v.F][x][0] + 2 * v.S);
			}
		}
	}
}
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 1 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 48 ms 257876 KB Output is correct
2 Correct 53 ms 261708 KB Output is correct
3 Correct 94 ms 264024 KB Output is correct
4 Correct 67 ms 261968 KB Output is correct
5 Correct 60 ms 261712 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 257876 KB Output is correct
2 Correct 53 ms 261708 KB Output is correct
3 Correct 94 ms 264024 KB Output is correct
4 Correct 67 ms 261968 KB Output is correct
5 Correct 60 ms 261712 KB Output is correct
6 Correct 47 ms 261712 KB Output is correct
7 Correct 84 ms 261964 KB Output is correct
8 Correct 48 ms 261760 KB Output is correct
9 Correct 54 ms 261972 KB Output is correct
10 Correct 48 ms 261720 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 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 48 ms 257876 KB Output is correct
7 Correct 53 ms 261708 KB Output is correct
8 Correct 94 ms 264024 KB Output is correct
9 Correct 67 ms 261968 KB Output is correct
10 Correct 60 ms 261712 KB Output is correct
11 Correct 47 ms 261712 KB Output is correct
12 Correct 84 ms 261964 KB Output is correct
13 Correct 48 ms 261760 KB Output is correct
14 Correct 54 ms 261972 KB Output is correct
15 Correct 48 ms 261720 KB Output is correct
16 Correct 133 ms 313632 KB Output is correct
17 Correct 720 ms 535380 KB Output is correct
18 Correct 1872 ms 312032 KB Output is correct
19 Correct 128 ms 313428 KB Output is correct
20 Correct 107 ms 313472 KB Output is correct
21 Execution timed out 3092 ms 756924 KB Time limit exceeded
22 Halted 0 ms 0 KB -