oj.uz

Submission #952150

# Submission time Handle Problem Language Result Execution time Memory
952150 2024-03-23T06:47:00 Z vjudge1 Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 784328 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){
	memset(dp[now],0x3f,sizeof(dp[now]));
	son[now]=1;
	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);
			}
		}
	}
}
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++){
		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:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<q[now].size();i++){
      |              ~^~~~~~~~~~~~~~
museum.cpp: At global scope:
museum.cpp:76:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   76 | int main(){
      |          ^
museum.cpp:76:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
museum.cpp:76:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
museum.cpp:76:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
museum.cpp: In function 'int main()':
museum.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d%d%d",&n,&k,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
museum.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2904 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 352 ms 784028 KB Output is correct
2 Correct 244 ms 783956 KB Output is correct
3 Correct 340 ms 784088 KB Output is correct
4 Correct 274 ms 783956 KB Output is correct
5 Correct 257 ms 783956 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 784028 KB Output is correct
2 Correct 244 ms 783956 KB Output is correct
3 Correct 340 ms 784088 KB Output is correct
4 Correct 274 ms 783956 KB Output is correct
5 Correct 257 ms 783956 KB Output is correct
6 Correct 255 ms 783952 KB Output is correct
7 Correct 302 ms 784184 KB Output is correct
8 Correct 240 ms 783952 KB Output is correct
9 Correct 239 ms 783944 KB Output is correct
10 Correct 241 ms 783952 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2904 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 352 ms 784028 KB Output is correct
7 Correct 244 ms 783956 KB Output is correct
8 Correct 340 ms 784088 KB Output is correct
9 Correct 274 ms 783956 KB Output is correct
10 Correct 257 ms 783956 KB Output is correct
11 Correct 255 ms 783952 KB Output is correct
12 Correct 302 ms 784184 KB Output is correct
13 Correct 240 ms 783952 KB Output is correct
14 Correct 239 ms 783944 KB Output is correct
15 Correct 241 ms 783952 KB Output is correct
16 Correct 334 ms 783912 KB Output is correct
17 Correct 1060 ms 783808 KB Output is correct
18 Correct 2902 ms 784328 KB Output is correct
19 Correct 316 ms 783868 KB Output is correct
20 Correct 295 ms 783952 KB Output is correct
21 Execution timed out 3057 ms 390336 KB Time limit exceeded
22 Halted 0 ms 0 KB -