oj.uz

Submission #951999

# Submission time Handle Problem Language Result Execution time Memory
951999 2024-03-23T03:34:17 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 757328 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define son v.first
#define len v.second
inline int read(){
	int re=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)){
		re=re*10+ch-'0';
		ch=getchar();
	}
	return re*f;
}
int dp[N][N][2];
int n,p,Son[N],rt;
vector<pair<int,int>> G[N];
inline void dfs(int now,int fa){
	dp[now][1][1]=dp[now][1][0]=0;
	Son[now]=1;
	for(auto&v:G[now]){
		if(son!=fa){
			dfs(son,now);
			Son[now]+=Son[son];
			for(int i=min(p,Son[now]);i>0;i--){
				if(i-1<=Son[son]){
					dp[now][i][1]=min(dp[now][i][1],dp[son][i-1][1]+len);
					dp[now][i][0]=min(dp[now][i][0],dp[son][i-1][0]+2*len);					
				}
				for(int j=min({p,Son[son],i});j>=0;j--){
					dp[now][i][0]=min(dp[now][i][0],dp[now][i-j][0]+dp[son][j][0]+2*len);
					dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][0]+dp[son][j][1]+len);
					dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][1]+dp[son][j][0]+2*len);
				}				
			}		
		}
	}
}
signed main(){
	n=read();p=read();rt=read();
	for(int i=1,x,y,z;i<n;i++){
		x=read();y=read();z=read();
		G[x].push_back(make_pair(y,z));
		G[y].push_back(make_pair(x,z));
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=p;j++){
			dp[i][j][1]=dp[i][j][0]=1e9;
		}
	}
	dfs(rt,0);
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=p;j++){
//			cout<<i<<" visit "<<j<<" :"<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
//		}
//	}
	printf("%d",min(dp[rt][p][1],dp[rt][p][0]));
}

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 53 ms 257872 KB Output is correct
2 Correct 50 ms 259924 KB Output is correct
3 Correct 108 ms 265928 KB Output is correct
4 Correct 80 ms 265656 KB Output is correct
5 Correct 68 ms 273204 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 257872 KB Output is correct
2 Correct 50 ms 259924 KB Output is correct
3 Correct 108 ms 265928 KB Output is correct
4 Correct 80 ms 265656 KB Output is correct
5 Correct 68 ms 273204 KB Output is correct
6 Correct 50 ms 269672 KB Output is correct
7 Correct 106 ms 269652 KB Output is correct
8 Correct 52 ms 269396 KB Output is correct
9 Correct 50 ms 271424 KB Output is correct
10 Correct 55 ms 271248 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 53 ms 257872 KB Output is correct
7 Correct 50 ms 259924 KB Output is correct
8 Correct 108 ms 265928 KB Output is correct
9 Correct 80 ms 265656 KB Output is correct
10 Correct 68 ms 273204 KB Output is correct
11 Correct 50 ms 269672 KB Output is correct
12 Correct 106 ms 269652 KB Output is correct
13 Correct 52 ms 269396 KB Output is correct
14 Correct 50 ms 271424 KB Output is correct
15 Correct 55 ms 271248 KB Output is correct
16 Correct 170 ms 319032 KB Output is correct
17 Correct 1047 ms 539012 KB Output is correct
18 Correct 2962 ms 320696 KB Output is correct
19 Correct 157 ms 318856 KB Output is correct
20 Correct 132 ms 320632 KB Output is correct
21 Execution timed out 3043 ms 757328 KB Time limit exceeded
22 Halted 0 ms 0 KB -