oj.uz

Submission #94466

# Submission time Handle Problem Language Result Execution time Memory
94466 2019-01-19T01:20:24 Z jasony123123 Museum (CEOI17_museum) C++11
80 / 100
 3000 ms 19352 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 = 1e15;
/**************************CEOI17 Day 0 P3 - Museum**************************************/
typedef vector<array<ll, 2>> dpvec;

int N, K, X;
dpvec dp[10001];
v<pii> adj[10001];

void update(dpvec &cur, dpvec &add, int cost, int biggest) {
	RFORE(cn, biggest, 1) {
		FOR(an, 1, add.size()) if (an + cn <= K) {
			if (cur[cn][0] != INF) {
				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);
			}
			if (cur[cn][1] != INF)
				minn(cur[cn + an][1], cur[cn][1] + add[an][0] + cost * 2);
		}
	}
}

int dfs(int x, int p) {
	int subsz = 1;
	v<int> nums;
	for (auto c : adj[x]) if (c.first != p) {
		subsz += dfs(c.first, x);
		nums.push_back(subsz);
	}

	// compute dp[x]
	dp[x].resize(min(K, subsz) + 1, { INF, INF });
	dp[x][1][0] = 0, dp[x][1][1] = 0;
	reverse(all(nums));
	for (auto c : adj[x]) if (c.first != p) {
		update(dp[x], dp[c.first], c.second, nums.back());
		nums.pop_back();
	}

	return subsz;
}

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 });
	}
	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 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2808 KB Output is correct
2 Correct 38 ms 2936 KB Output is correct
3 Correct 1448 ms 7988 KB Output is correct
4 Correct 467 ms 5624 KB Output is correct
5 Correct 130 ms 4600 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2808 KB Output is correct
2 Correct 38 ms 2936 KB Output is correct
3 Correct 1448 ms 7988 KB Output is correct
4 Correct 467 ms 5624 KB Output is correct
5 Correct 130 ms 4600 KB Output is correct
6 Correct 30 ms 2424 KB Output is correct
7 Correct 867 ms 7644 KB Output is correct
8 Correct 87 ms 1820 KB Output is correct
9 Correct 61 ms 1656 KB Output is correct
10 Correct 33 ms 1788 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 36 ms 2808 KB Output is correct
7 Correct 38 ms 2936 KB Output is correct
8 Correct 1448 ms 7988 KB Output is correct
9 Correct 467 ms 5624 KB Output is correct
10 Correct 130 ms 4600 KB Output is correct
11 Correct 30 ms 2424 KB Output is correct
12 Correct 867 ms 7644 KB Output is correct
13 Correct 87 ms 1820 KB Output is correct
14 Correct 61 ms 1656 KB Output is correct
15 Correct 33 ms 1788 KB Output is correct
16 Correct 231 ms 3656 KB Output is correct
17 Correct 850 ms 4864 KB Output is correct
18 Execution timed out 3050 ms 19352 KB Time limit exceeded
19 Halted 0 ms 0 KB -