oj.uz

Submission #951992

# Submission time Handle Problem Language Result Execution time Memory
951992 2024-03-23T03:30:55 Z vjudge1 Museum (CEOI17_museum) C++17
0 / 100
 266 ms 784472 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
int n,k,x,inu,inv,inw,dp[MAXN][MAXN][2],siz[MAXN],minn=INT_MAX;
vector <pair<int,int> > lis[MAXN];
void dfs(int u,int fa){
	dp[u][1][0]=0;
	dp[u][1][1]=0;
	siz[u]=1;
	for(auto it:lis[u]){
		int v=it.first;
		int w=it.second;
		if(v==fa) continue;
		dfs(v,u);
		
		for(int i=min(siz[u],k);i>=1;i--)
			for(int j=1;j<=min(siz[v],i-1);j++){
				//if(i-j-2){
					dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v][j][0]+w*2);
					dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][1]+dp[v][j][0]+w*2);
					dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][0]+dp[v][j][1]+w);
			}
		siz[u]+=siz[v];
	}
}
int main(){
//	freopen("museum.in","r",stdin);
//	freopen("museum.out","w",stdout);
	scanf("%d%d%d",&n,&k,&x);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&inu,&inv,&inw);
		lis[inu].push_back({inv,inw});
		lis[inv].push_back({inu,inw});
	}
	memset(dp,0x3f,sizeof dp);
	dfs(x,-1);
/*	for(int i=1;i<=n;i++){
		printf("I%d\n",i);
		for(int j=1;j<=k;j++) printf("%d %d   ",dp[i][j][0],dp[i][j][1]);
		printf("\n");
  }*/
	printf("%d",min(dp[x][k][0],dp[x][k][1]));
}

Compilation message

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

Subtask #1
0 / 20.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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