oj.uz

Submission #253404

# Submission time Handle Problem Language Result Execution time Memory
253404 2020-07-28T01:12:17 Z super_j6 Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784248 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int inf = 0x3f3f3f3f;
const int mxn = 10001;
int n, k, x;
int dp[mxn][mxn][2];
vector<pi> g[mxn];
 
void dfs(int c, int p){
	memset(dp[c], inf, sizeof(dp[c]));
	dp[c][1][0] = dp[c][1][1] = 0;
	for(pi i : g[c]){
		if(i.f == p) continue;
		dfs(i.f, c);
		for(int j = k; ~j; j--){
			int ret[2] = {inf, inf};
			for(int l = 0; l <= j; l++){
				ret[0] = min(ret[0], dp[c][j - l][0] + dp[i.f][l][0] + 2 * i.s);
				ret[1] = min(ret[1], dp[c][j - l][1] + dp[i.f][l][0] + 2 * i.s);
				ret[1] = min(ret[1], dp[c][j - l][0] + dp[i.f][l][1] + i.s);
			}
			for(int l = 0; l < 2; l++){
				dp[c][j][l] = min(dp[c][j][l], ret[l]);
			}
		}
	}/*
	cout << c + 1 << endl;
	for(int i = 0; i <= k; i++) cout << dp[c][i][0] << " " << dp[c][i][1] << " | ";
	cout << endl;
	*/
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> x;
	x--;
	
	for(int i = 0; i < n - 1; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	dfs(x, -1);
	
	cout << dp[x][k][1] << endl;
 
	return 0;
}

Compilation message

museum.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
museum.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2176 KB Output is correct
2 Correct 2 ms 2176 KB Output is correct
3 Correct 2 ms 2176 KB Output is correct
4 Correct 2 ms 2176 KB Output is correct
5 Correct 1 ms 2176 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 783920 KB Output is correct
2 Correct 552 ms 784112 KB Output is correct
3 Correct 565 ms 784248 KB Output is correct
4 Correct 546 ms 784212 KB Output is correct
5 Correct 556 ms 784120 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 783920 KB Output is correct
2 Correct 552 ms 784112 KB Output is correct
3 Correct 565 ms 784248 KB Output is correct
4 Correct 546 ms 784212 KB Output is correct
5 Correct 556 ms 784120 KB Output is correct
6 Correct 588 ms 783992 KB Output is correct
7 Correct 576 ms 784248 KB Output is correct
8 Correct 591 ms 784248 KB Output is correct
9 Correct 561 ms 784120 KB Output is correct
10 Correct 559 ms 783992 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2176 KB Output is correct
2 Correct 2 ms 2176 KB Output is correct
3 Correct 2 ms 2176 KB Output is correct
4 Correct 2 ms 2176 KB Output is correct
5 Correct 1 ms 2176 KB Output is correct
6 Correct 545 ms 783920 KB Output is correct
7 Correct 552 ms 784112 KB Output is correct
8 Correct 565 ms 784248 KB Output is correct
9 Correct 546 ms 784212 KB Output is correct
10 Correct 556 ms 784120 KB Output is correct
11 Correct 588 ms 783992 KB Output is correct
12 Correct 576 ms 784248 KB Output is correct
13 Correct 591 ms 784248 KB Output is correct
14 Correct 561 ms 784120 KB Output is correct
15 Correct 559 ms 783992 KB Output is correct
16 Execution timed out 3080 ms 212700 KB Time limit exceeded
17 Halted 0 ms 0 KB -