oj.uz

Submission #952144

# Submission time Handle Problem Language Result Execution time Memory
952144 2024-03-23T06:41:08 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 784356 KB 
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#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:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
museum.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
museum.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
museum.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
museum.cpp:56:24: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   56 | void dfs(int now,int fa){
      |                        ^
museum.cpp:56:24: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
museum.cpp:56:24: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
museum.cpp:56:24: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
museum.cpp: In function 'void dfs(int, int)':
museum.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<q[now].size();i++){
      |              ~^~~~~~~~~~~~~~
museum.cpp: At global scope:
museum.cpp:78:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   78 | int main(){
      |          ^
museum.cpp:78:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
museum.cpp:78:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
museum.cpp:78:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
museum.cpp: In function 'int main()':
museum.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d%d%d",&n,&k,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
museum.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 783440 KB Output is correct
2 Correct 308 ms 783620 KB Output is correct
3 Correct 218 ms 783492 KB Output is correct
4 Correct 221 ms 783440 KB Output is correct
5 Correct 227 ms 783444 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 783952 KB Output is correct
2 Correct 225 ms 783872 KB Output is correct
3 Correct 296 ms 784328 KB Output is correct
4 Correct 253 ms 783996 KB Output is correct
5 Correct 246 ms 784356 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 783952 KB Output is correct
2 Correct 225 ms 783872 KB Output is correct
3 Correct 296 ms 784328 KB Output is correct
4 Correct 253 ms 783996 KB Output is correct
5 Correct 246 ms 784356 KB Output is correct
6 Correct 225 ms 783952 KB Output is correct
7 Correct 275 ms 784180 KB Output is correct
8 Correct 229 ms 783924 KB Output is correct
9 Correct 227 ms 783844 KB Output is correct
10 Correct 225 ms 783956 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 783440 KB Output is correct
2 Correct 308 ms 783620 KB Output is correct
3 Correct 218 ms 783492 KB Output is correct
4 Correct 221 ms 783440 KB Output is correct
5 Correct 227 ms 783444 KB Output is correct
6 Correct 231 ms 783952 KB Output is correct
7 Correct 225 ms 783872 KB Output is correct
8 Correct 296 ms 784328 KB Output is correct
9 Correct 253 ms 783996 KB Output is correct
10 Correct 246 ms 784356 KB Output is correct
11 Correct 225 ms 783952 KB Output is correct
12 Correct 275 ms 784180 KB Output is correct
13 Correct 229 ms 783924 KB Output is correct
14 Correct 227 ms 783844 KB Output is correct
15 Correct 225 ms 783956 KB Output is correct
16 Correct 316 ms 783992 KB Output is correct
17 Correct 1037 ms 784036 KB Output is correct
18 Correct 2912 ms 784144 KB Output is correct
19 Correct 295 ms 784160 KB Output is correct
20 Correct 277 ms 784060 KB Output is correct
21 Execution timed out 3051 ms 783872 KB Time limit exceeded
22 Halted 0 ms 0 KB -