oj.uz

Submission #951990

# Submission time Handle Problem Language Result Execution time Memory
951990 2024-03-23T03:30:01 Z vjudge1 Museum (CEOI17_museum) C++14
20 / 100
 844 ms 422180 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct edge{
	int to,w;
};
int dp[N][N],son[N],f[N][N];
vector<edge>G[N];
int n,k,x;
inline void dfs(int u,int fa){
	son[u]=1;
	dp[u][0]=dp[u][1]=0;
	for(auto v:G[u]){
		if(v.to==fa) continue;
		dfs(v.to,u);son[u]+=son[v.to];
		for(int i=min(k,son[u]);i>=1;i--)
			for(int j=min(i-1,son[v.to]);j>=1;j--){
				if(dp[u][i]-f[u][i]>=dp[u][i-j]+dp[v.to][j]+v.w*2-max(f[u][i-j],f[v.to][j]+v.w)){
					dp[u][i]=dp[u][i-j]+dp[v.to][j]+v.w*2;
					f[u][i]=max(f[u][i-j],f[v.to][j]+v.w);
				}
			}
	}
}
int main(){
	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);
		G[u].push_back({v,w});G[v].push_back({u,w});
	}
	dfs(x,0);
	printf("%d",dp[x][k]-f[x][k]);
	return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 396220 KB Output is correct
2 Correct 334 ms 396236 KB Output is correct
3 Correct 136 ms 396368 KB Output is correct
4 Correct 141 ms 396388 KB Output is correct
5 Correct 364 ms 396372 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 422180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 422180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 396220 KB Output is correct
2 Correct 334 ms 396236 KB Output is correct
3 Correct 136 ms 396368 KB Output is correct
4 Correct 141 ms 396388 KB Output is correct
5 Correct 364 ms 396372 KB Output is correct
6 Incorrect 202 ms 422180 KB Output isn't correct
7 Halted 0 ms 0 KB -