oj.uz

Submission #952157

# Submission time Handle Problem Language Result Execution time Memory
952157 2024-03-23T07:18:21 Z vjudge1 Museum (CEOI17_museum) C++14
100 / 100
 501 ms 784980 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N=1e4+5;
int n,k,x,son[N];
int dp[N][N][2];
vector<pair<int,int> >g[N];
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch < '0' || ch > '9'){
        if(ch=='-') f = -1;
        ch = getchar();
   }
   while(ch >='0' && ch <= '9'){
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
   }
   return x*f;
}
inline void dfs(int u,int fa){
	dp[u][1][0]=dp[u][1][1]=0;
	son[u]=1;
	for(auto v:g[u]){
		if(v.first==fa)continue;
		dfs(v.first,u);
		int mxi=min(k,son[u]);
		for(int i=mxi;i>=0;i--){
			int mxj=min(k-i,son[v.first]);
			for(int j=mxj;j>=0;j--){
				if(dp[u][i][0]+dp[v.first][j][0]+v.second*2>=0)dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v.first][j][0]+v.second*2);
				if(dp[u][i][0]+dp[v.first][j][1]+v.second>=0)dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][0]+dp[v.first][j][1]+v.second);
				if(dp[u][i][1]+dp[v.first][j][0]+v.second*2>=0)dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v.first][j][0]+v.second*2);
			}
		}
		son[u]+=son[v.first];
	}
}
int main(){
	memset(dp,0x7f,sizeof dp);
	n=read();
	k=read();
	x=read();
	for(int i=1,a,b,c;i<n;i++){
		a=read();
		b=read();
		c=read();
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(x,-1);
	cout<<min(dp[x][k][0],dp[x][k][1]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 784396 KB Output is correct
2 Correct 193 ms 784208 KB Output is correct
3 Correct 193 ms 784440 KB Output is correct
4 Correct 192 ms 784208 KB Output is correct
5 Correct 193 ms 784192 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784700 KB Output is correct
2 Correct 201 ms 784532 KB Output is correct
3 Correct 202 ms 784564 KB Output is correct
4 Correct 202 ms 784576 KB Output is correct
5 Correct 201 ms 784468 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 784700 KB Output is correct
2 Correct 201 ms 784532 KB Output is correct
3 Correct 202 ms 784564 KB Output is correct
4 Correct 202 ms 784576 KB Output is correct
5 Correct 201 ms 784468 KB Output is correct
6 Correct 201 ms 784428 KB Output is correct
7 Correct 201 ms 784660 KB Output is correct
8 Correct 205 ms 784468 KB Output is correct
9 Correct 205 ms 784500 KB Output is correct
10 Correct 201 ms 784464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 784396 KB Output is correct
2 Correct 193 ms 784208 KB Output is correct
3 Correct 193 ms 784440 KB Output is correct
4 Correct 192 ms 784208 KB Output is correct
5 Correct 193 ms 784192 KB Output is correct
6 Correct 209 ms 784700 KB Output is correct
7 Correct 201 ms 784532 KB Output is correct
8 Correct 202 ms 784564 KB Output is correct
9 Correct 202 ms 784576 KB Output is correct
10 Correct 201 ms 784468 KB Output is correct
11 Correct 201 ms 784428 KB Output is correct
12 Correct 201 ms 784660 KB Output is correct
13 Correct 205 ms 784468 KB Output is correct
14 Correct 205 ms 784500 KB Output is correct
15 Correct 201 ms 784464 KB Output is correct
16 Correct 227 ms 784648 KB Output is correct
17 Correct 316 ms 784724 KB Output is correct
18 Correct 235 ms 784468 KB Output is correct
19 Correct 277 ms 784468 KB Output is correct
20 Correct 232 ms 784660 KB Output is correct
21 Correct 383 ms 784724 KB Output is correct
22 Correct 356 ms 784488 KB Output is correct
23 Correct 501 ms 784876 KB Output is correct
24 Correct 361 ms 784468 KB Output is correct
25 Correct 416 ms 784980 KB Output is correct