oj.uz

Submission #980391

# Submission time Handle Problem Language Result Execution time Memory
980391 2024-05-12T06:59:11 Z hqminhuwu Museum (CEOI17_museum) C++14
100 / 100
 188 ms 167572 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 1e4 + 5;
const ll oo = 3e8;
const ll mod = 1e9 + 7; // 998244353;

void minz (int &u, int v){
	if (u > v)
		u = v;
}

vector <int> dp[N][2];
vector <pii> a[N];


void dfs (int u, int p){
	dp[u][0].pb(0);
	dp[u][1].pb(0);

	for (pii t : a[u]){
		int v = t.st, w = t.nd;
		if (v == p) continue;
		dfs(v, u);
		int lmt = dp[u][0].size();
		forf (i, 0, dp[v][0].size()){
			dp[u][0].pb(oo);
			dp[u][1].pb(oo);
		}

		ford (i, lmt - 1, 0){
			forf (j, 0, dp[v][0].size()){
			//	cout << i << " " << j << " " << i + j + 1 << "\n";
				minz(dp[u][0][i + j + 1], dp[u][0][i] + dp[v][0][j] + 2 * w);
				minz(dp[u][1][i + j + 1], dp[u][1][i] + dp[v][0][j] + 2 * w);
				minz(dp[u][1][i + j + 1], dp[u][0][i] + dp[v][1][j] + w);

			}
		}

		
	}
}

int n, k, root, u, v, w;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> k >> root;

	forf (i, 1, n){
		cin >> u >> v >> w;
		a[u].pb({v, w});
		a[v].pb({u, w});
	}

	dfs(root, root);

	cout << dp[root][1][k - 1];

	return 0;
}
/*



*/

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:11:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
museum.cpp:44:3: note: in expansion of macro 'forf'
   44 |   forf (i, 0, dp[v][0].size()){
      |   ^~~~
museum.cpp:11:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
museum.cpp:50:4: note: in expansion of macro 'forf'
   50 |    forf (j, 0, dp[v][0].size()){
      |    ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4200 KB Output is correct
2 Correct 88 ms 4500 KB Output is correct
3 Correct 188 ms 157868 KB Output is correct
4 Correct 118 ms 55360 KB Output is correct
5 Correct 95 ms 15688 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4200 KB Output is correct
2 Correct 88 ms 4500 KB Output is correct
3 Correct 188 ms 157868 KB Output is correct
4 Correct 118 ms 55360 KB Output is correct
5 Correct 95 ms 15688 KB Output is correct
6 Correct 87 ms 3420 KB Output is correct
7 Correct 153 ms 99000 KB Output is correct
8 Correct 150 ms 2536 KB Output is correct
9 Correct 126 ms 2680 KB Output is correct
10 Correct 97 ms 3212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 96 ms 4200 KB Output is correct
7 Correct 88 ms 4500 KB Output is correct
8 Correct 188 ms 157868 KB Output is correct
9 Correct 118 ms 55360 KB Output is correct
10 Correct 95 ms 15688 KB Output is correct
11 Correct 87 ms 3420 KB Output is correct
12 Correct 153 ms 99000 KB Output is correct
13 Correct 150 ms 2536 KB Output is correct
14 Correct 126 ms 2680 KB Output is correct
15 Correct 97 ms 3212 KB Output is correct
16 Correct 99 ms 5068 KB Output is correct
17 Correct 93 ms 4760 KB Output is correct
18 Correct 132 ms 66124 KB Output is correct
19 Correct 124 ms 2388 KB Output is correct
20 Correct 95 ms 3636 KB Output is correct
21 Correct 151 ms 96532 KB Output is correct
22 Correct 86 ms 4704 KB Output is correct
23 Correct 117 ms 2576 KB Output is correct
24 Correct 84 ms 3504 KB Output is correct
25 Correct 188 ms 167572 KB Output is correct