oj.uz

Submission #94468

# Submission time Handle Problem Language Result Execution time Memory
94468 2019-01-19T01:47:42 Z jasony123123 Museum (CEOI17_museum) C++11
80 / 100
 3000 ms 19480 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) {
			while (cur.size() <= cn + an) cur.push_back({ INF,INF });
			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;
	dp[x] = { {INF,INF}, {0,0} };
	for (auto c : adj[x]) if (c.first != p) {
		subsz += dfs(c.first, x);
		update(dp[x], dp[c.first], c.second, subsz);
	}
	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;
}

Compilation message

museum.cpp: In function 'void update(dpvec&, dpvec&, int, int)':
museum.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (cur.size() <= cn + an) cur.push_back({ INF,INF });
           ~~~~~~~~~~~^~~~~~~~~~

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 888 KB Output is correct
4 Correct 2 ms 888 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 57 ms 4572 KB Output is correct
2 Correct 61 ms 4572 KB Output is correct
3 Correct 2199 ms 10264 KB Output is correct
4 Correct 727 ms 8696 KB Output is correct
5 Correct 212 ms 7888 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4572 KB Output is correct
2 Correct 61 ms 4572 KB Output is correct
3 Correct 2199 ms 10264 KB Output is correct
4 Correct 727 ms 8696 KB Output is correct
5 Correct 212 ms 7888 KB Output is correct
6 Correct 49 ms 3192 KB Output is correct
7 Correct 1328 ms 9444 KB Output is correct
8 Correct 176 ms 1656 KB Output is correct
9 Correct 120 ms 1748 KB Output is correct
10 Correct 51 ms 2040 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 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 57 ms 4572 KB Output is correct
7 Correct 61 ms 4572 KB Output is correct
8 Correct 2199 ms 10264 KB Output is correct
9 Correct 727 ms 8696 KB Output is correct
10 Correct 212 ms 7888 KB Output is correct
11 Correct 49 ms 3192 KB Output is correct
12 Correct 1328 ms 9444 KB Output is correct
13 Correct 176 ms 1656 KB Output is correct
14 Correct 120 ms 1748 KB Output is correct
15 Correct 51 ms 2040 KB Output is correct
16 Correct 479 ms 7440 KB Output is correct
17 Correct 1916 ms 9928 KB Output is correct
18 Execution timed out 3049 ms 19480 KB Time limit exceeded
19 Halted 0 ms 0 KB -