oj.uz

Submission #864084

# Submission time Handle Problem Language Result Execution time Memory
864084 2023-10-22T02:57:27 Z phoenix0423 Museum (CEOI17_museum) C++17
100 / 100
 470 ms 320520 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const ll INF = 1e18;

ll n, k, st;
vector<pll> adj[maxn];
vector<ll> dp[maxn][2];

vector<ll> total_min(vector<ll> a, vector<ll> b, int ded = 0){
	vector<ll> nw(a.size() + b.size() - 1, INF);
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < b.size(); j++){
			nw[i + j] = min(nw[i + j], a[i] + b[j] - ded);
		}
	}
	return nw;
}

void chgmin(vector<ll> &a, vector<ll> b){
	int sz = max(a.size(), b.size());
	a.resize(sz, INF);
	b.resize(sz, INF);
	for(int i = 0; i < sz; i++) a[i] = min(a[i], b[i]);
}
void dfs(int pos, int prev, int plen){
	dp[pos][0] = {INF, plen};
	dp[pos][1] = {INF, plen * 2};
	for(auto [x, w] : adj[pos]){
		if(x == prev) continue;
		dfs(x, pos, w);
		dp[pos][0] = total_min(dp[pos][0], dp[x][1]);
		chgmin(dp[pos][0], total_min(dp[pos][1], dp[x][0], plen));
		dp[pos][1] = total_min(dp[pos][1], dp[x][1]);
	}
	dp[pos][0][0] = dp[pos][1][0] = 0;
}

int main(void){
	fastio;
	cin>>n>>k>>st;
	st--;
	for(int i = 0; i < n - 1; i++){
		int a, b, c;
		cin>>a>>b>>c;
		a--, b--;
		adj[a].eb(b, c);
		adj[b].eb(a, c);
	}
	dfs(st, -1, 0);
	cout<<min(dp[st][0][k], dp[st][1][k])<<"\n";
}

Compilation message

museum.cpp: In function 'std::vector<long long int> total_min(std::vector<long long int>, std::vector<long long int>, int)':
museum.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < a.size(); i++){
      |                 ~~^~~~~~~~~~
museum.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int j = 0; j < b.size(); j++){
      |                  ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 19228 KB Output is correct
2 Correct 153 ms 20248 KB Output is correct
3 Correct 382 ms 320520 KB Output is correct
4 Correct 227 ms 110268 KB Output is correct
5 Correct 171 ms 37864 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 19228 KB Output is correct
2 Correct 153 ms 20248 KB Output is correct
3 Correct 382 ms 320520 KB Output is correct
4 Correct 227 ms 110268 KB Output is correct
5 Correct 171 ms 37864 KB Output is correct
6 Correct 153 ms 18200 KB Output is correct
7 Correct 304 ms 199508 KB Output is correct
8 Correct 470 ms 16260 KB Output is correct
9 Correct 395 ms 16528 KB Output is correct
10 Correct 180 ms 18204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 3 ms 14548 KB Output is correct
3 Correct 3 ms 14428 KB Output is correct
4 Correct 4 ms 14512 KB Output is correct
5 Correct 3 ms 14428 KB Output is correct
6 Correct 157 ms 19228 KB Output is correct
7 Correct 153 ms 20248 KB Output is correct
8 Correct 382 ms 320520 KB Output is correct
9 Correct 227 ms 110268 KB Output is correct
10 Correct 171 ms 37864 KB Output is correct
11 Correct 153 ms 18200 KB Output is correct
12 Correct 304 ms 199508 KB Output is correct
13 Correct 470 ms 16260 KB Output is correct
14 Correct 395 ms 16528 KB Output is correct
15 Correct 180 ms 18204 KB Output is correct
16 Correct 157 ms 20984 KB Output is correct
17 Correct 154 ms 20556 KB Output is correct
18 Correct 241 ms 127748 KB Output is correct
19 Correct 382 ms 16296 KB Output is correct
20 Correct 163 ms 18608 KB Output is correct
21 Correct 289 ms 183636 KB Output is correct
22 Correct 153 ms 20160 KB Output is correct
23 Correct 369 ms 16408 KB Output is correct
24 Correct 168 ms 18164 KB Output is correct
25 Correct 377 ms 308488 KB Output is correct