oj.uz

Submission #952006

# Submission time Handle Problem Language Result Execution time Memory
952006 2024-03-23T03:38:10 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 784376 KB 
#include <bits/stdc++.h>
using namespace std;
int n,k,x,tim[10005],dp[10001][10001][2],son[10005];
struct l{
	int tar,wei;
};
vector<l>q[10005];
void dfs(int now,int fa){
	son[now]=1;
	dp[now][0][0]=0;
	dp[now][0][1]=0;
	dp[now][1][1]=0;
	dp[now][1][0]=0;
	for(int i=0;i<q[now].size();i++){
		if(q[now][i].tar==fa){
			continue;
		} 
		dfs(q[now][i].tar,now);
		son[now]+=son[q[now][i].tar];
		for(int j=min(k,son[now]);j>=2;j--){
			for(int l=0;l<=min(j,son[q[now][i].tar]);l++){
				dp[now][j][0]=min(dp[now][j][0],dp[now][j-l][0]+dp[q[now][i].tar][l][0]+2*q[now][i].wei);
				dp[now][j][1]=min(dp[now][j][1],dp[now][j-l][0]+dp[q[now][i].tar][l][1]+q[now][i].wei);
				dp[now][j][1]=min(dp[now][j][1],dp[now][j-l][1]+dp[q[now][i].tar][l][0]+2*q[now][i].wei);
			}
		//	cout<<now<<" "<<j<<" "<<dp[now][j][0]<<" "<<dp[now][j][1]<<endl;
		}
	}
}
int main(){
//	freopen("museum.in","r",stdin);
//	freopen("museum.out","w",stdout);
	memset(dp,0x3f,sizeof(dp));
	scanf("%d%d%d",&n,&k,&x);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		q[u].push_back({v,w});
		q[v].push_back({u,w});
	}
	dfs(x,0);
	printf("%d",min(dp[x][k][0],dp[x][k][1]));
	return 0;
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<q[now].size();i++){
      |              ~^~~~~~~~~~~~~~
museum.cpp: In function 'int main()':
museum.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d%d",&n,&k,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
museum.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 783480 KB Output is correct
2 Correct 210 ms 783600 KB Output is correct
3 Correct 211 ms 783544 KB Output is correct
4 Correct 259 ms 783444 KB Output is correct
5 Correct 212 ms 783540 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 783952 KB Output is correct
2 Correct 296 ms 784216 KB Output is correct
3 Correct 290 ms 784376 KB Output is correct
4 Correct 264 ms 783956 KB Output is correct
5 Correct 334 ms 783956 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 783952 KB Output is correct
2 Correct 296 ms 784216 KB Output is correct
3 Correct 290 ms 784376 KB Output is correct
4 Correct 264 ms 783956 KB Output is correct
5 Correct 334 ms 783956 KB Output is correct
6 Correct 226 ms 783956 KB Output is correct
7 Correct 291 ms 784316 KB Output is correct
8 Correct 223 ms 783952 KB Output is correct
9 Correct 317 ms 784048 KB Output is correct
10 Correct 223 ms 783956 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 783480 KB Output is correct
2 Correct 210 ms 783600 KB Output is correct
3 Correct 211 ms 783544 KB Output is correct
4 Correct 259 ms 783444 KB Output is correct
5 Correct 212 ms 783540 KB Output is correct
6 Correct 226 ms 783952 KB Output is correct
7 Correct 296 ms 784216 KB Output is correct
8 Correct 290 ms 784376 KB Output is correct
9 Correct 264 ms 783956 KB Output is correct
10 Correct 334 ms 783956 KB Output is correct
11 Correct 226 ms 783956 KB Output is correct
12 Correct 291 ms 784316 KB Output is correct
13 Correct 223 ms 783952 KB Output is correct
14 Correct 317 ms 784048 KB Output is correct
15 Correct 223 ms 783956 KB Output is correct
16 Correct 331 ms 784024 KB Output is correct
17 Correct 1206 ms 783864 KB Output is correct
18 Execution timed out 3077 ms 784016 KB Time limit exceeded
19 Halted 0 ms 0 KB -