oj.uz

Submission #94508

# Submission time Handle Problem Language Result Execution time Memory
94508 2019-01-19T15:50:09 Z jasony123123 Museum (CEOI17_museum) C++11
100 / 100
 708 ms 784376 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e12;
/**************************CEOI17 Day 0 P3 - Museum**************************************/
int N, K, X, treesz[10001];
int dp[10001][10001][2];
v<pii> adj[10001];

void update(int cur[10001][2], int cursz, int add[10001][2], int addsz, int cost) {
	RFORE(cn, cursz, 1) {
		FORE(an, 1, addsz) if (cn + an <= K) {
			minn(cur[cn + an][0], cur[cn][0] + add[an][0] + cost * 2);
			minn(cur[cn + an][1], cur[cn][0] + add[an][1] + cost);
			minn(cur[cn + an][1], cur[cn][1] + add[an][0] + cost * 2);
		}
	}
}

int dfs(int x, int p) {
	dp[x][1][0] = 0, dp[x][1][1] = 0;
	treesz[x] = 1;
	for (auto c : adj[x]) if (c.first != p) {
		int tmp = dfs(c.first, x);
		update(dp[x], min(K - 1, treesz[x]), dp[c.first], min(K - 1, treesz[c.first]), c.second);
		treesz[x] += tmp;
	}
	return treesz[x];
}

int main() {
	io();
	cin >> N >> K >> X;
	FOR(i, 0, N - 1) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({ b,c }), adj[b].push_back({ a,c });
	}
	memset(dp, 0x3F3F3F3F, sizeof dp);
	dfs(X, -1);
	cout << dp[X][K][1] << "\n";
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 783512 KB Output is correct
2 Correct 528 ms 783580 KB Output is correct
3 Correct 522 ms 783480 KB Output is correct
4 Correct 592 ms 783736 KB Output is correct
5 Correct 594 ms 783612 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 783940 KB Output is correct
2 Correct 547 ms 784088 KB Output is correct
3 Correct 608 ms 784248 KB Output is correct
4 Correct 594 ms 784120 KB Output is correct
5 Correct 528 ms 784016 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 783940 KB Output is correct
2 Correct 547 ms 784088 KB Output is correct
3 Correct 608 ms 784248 KB Output is correct
4 Correct 594 ms 784120 KB Output is correct
5 Correct 528 ms 784016 KB Output is correct
6 Correct 526 ms 784016 KB Output is correct
7 Correct 555 ms 784248 KB Output is correct
8 Correct 547 ms 784092 KB Output is correct
9 Correct 532 ms 784140 KB Output is correct
10 Correct 610 ms 784024 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 783512 KB Output is correct
2 Correct 528 ms 783580 KB Output is correct
3 Correct 522 ms 783480 KB Output is correct
4 Correct 592 ms 783736 KB Output is correct
5 Correct 594 ms 783612 KB Output is correct
6 Correct 533 ms 783940 KB Output is correct
7 Correct 547 ms 784088 KB Output is correct
8 Correct 608 ms 784248 KB Output is correct
9 Correct 594 ms 784120 KB Output is correct
10 Correct 528 ms 784016 KB Output is correct
11 Correct 526 ms 784016 KB Output is correct
12 Correct 555 ms 784248 KB Output is correct
13 Correct 547 ms 784092 KB Output is correct
14 Correct 532 ms 784140 KB Output is correct
15 Correct 610 ms 784024 KB Output is correct
16 Correct 570 ms 784092 KB Output is correct
17 Correct 662 ms 784060 KB Output is correct
18 Correct 608 ms 784120 KB Output is correct
19 Correct 594 ms 784052 KB Output is correct
20 Correct 550 ms 784200 KB Output is correct
21 Correct 708 ms 784320 KB Output is correct
22 Correct 666 ms 784120 KB Output is correct
23 Correct 673 ms 784252 KB Output is correct
24 Correct 667 ms 784248 KB Output is correct
25 Correct 692 ms 784376 KB Output is correct