oj.uz

Submission #94465

# Submission time Handle Problem Language Result Execution time Memory
94465 2019-01-19T01:17:36 Z jasony123123 Museum (CEOI17_museum) C++11
80 / 100
 3000 ms 30584 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) {
	RFORE(cn, cur.size() - 1, 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;
	for (auto c : adj[x]) if (c.first != p)
		subsz += dfs(c.first, x);

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

	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 936 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2808 KB Output is correct
2 Correct 17 ms 2808 KB Output is correct
3 Correct 54 ms 7672 KB Output is correct
4 Correct 38 ms 5496 KB Output is correct
5 Correct 30 ms 4728 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2808 KB Output is correct
2 Correct 17 ms 2808 KB Output is correct
3 Correct 54 ms 7672 KB Output is correct
4 Correct 38 ms 5496 KB Output is correct
5 Correct 30 ms 4728 KB Output is correct
6 Correct 16 ms 2552 KB Output is correct
7 Correct 53 ms 7416 KB Output is correct
8 Correct 11 ms 1912 KB Output is correct
9 Correct 10 ms 1784 KB Output is correct
10 Correct 13 ms 2040 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 936 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 17 ms 2808 KB Output is correct
7 Correct 17 ms 2808 KB Output is correct
8 Correct 54 ms 7672 KB Output is correct
9 Correct 38 ms 5496 KB Output is correct
10 Correct 30 ms 4728 KB Output is correct
11 Correct 16 ms 2552 KB Output is correct
12 Correct 53 ms 7416 KB Output is correct
13 Correct 11 ms 1912 KB Output is correct
14 Correct 10 ms 1784 KB Output is correct
15 Correct 13 ms 2040 KB Output is correct
16 Correct 99 ms 3900 KB Output is correct
17 Correct 585 ms 5008 KB Output is correct
18 Correct 1692 ms 30584 KB Output is correct
19 Correct 43 ms 1912 KB Output is correct
20 Correct 65 ms 2552 KB Output is correct
21 Execution timed out 3046 ms 24284 KB Time limit exceeded
22 Halted 0 ms 0 KB -