oj.uz

Submission #94507

# Submission time Handle Problem Language Result Execution time Memory
94507 2019-01-19T15:41:27 Z jasony123123 Museum (CEOI17_museum) C++11
80 / 100
 3000 ms 784664 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**************************************/
typedef vector<array<ll, 2>> dpvec;

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

void update(dpvec &cur, int cursz, dpvec &add, 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].resize(K + 1, { INF,INF });
	dp[x][1][0] = 0, dp[x][1][1] = 0;
	treesz[x] = 1;
	for (auto c : adj[x]) if (c.first != p) {
		treesz[x] += dfs(c.first, x);
		update(dp[x], min(K - 1, treesz[x]), dp[c.first], min(K - 1, treesz[c.first]), c.second);
	}
	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 });
	}
	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 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 760 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 35 ms 17400 KB Output is correct
2 Correct 35 ms 17400 KB Output is correct
3 Correct 109 ms 17656 KB Output is correct
4 Correct 74 ms 17272 KB Output is correct
5 Correct 57 ms 17148 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17400 KB Output is correct
2 Correct 35 ms 17400 KB Output is correct
3 Correct 109 ms 17656 KB Output is correct
4 Correct 74 ms 17272 KB Output is correct
5 Correct 57 ms 17148 KB Output is correct
6 Correct 29 ms 17272 KB Output is correct
7 Correct 102 ms 17528 KB Output is correct
8 Correct 27 ms 17272 KB Output is correct
9 Correct 26 ms 17272 KB Output is correct
10 Correct 28 ms 17400 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 35 ms 17400 KB Output is correct
7 Correct 35 ms 17400 KB Output is correct
8 Correct 109 ms 17656 KB Output is correct
9 Correct 74 ms 17272 KB Output is correct
10 Correct 57 ms 17148 KB Output is correct
11 Correct 29 ms 17272 KB Output is correct
12 Correct 102 ms 17528 KB Output is correct
13 Correct 27 ms 17272 KB Output is correct
14 Correct 26 ms 17272 KB Output is correct
15 Correct 28 ms 17400 KB Output is correct
16 Correct 263 ms 158328 KB Output is correct
17 Correct 1738 ms 784664 KB Output is correct
18 Execution timed out 3048 ms 138892 KB Time limit exceeded
19 Halted 0 ms 0 KB -