oj.uz

Submission #241844

# Submission time Handle Problem Language Result Execution time Memory
241844 2020-06-25T22:36:08 Z ChrisT Museum (CEOI17_museum) C++17
100 / 100
 624 ms 784760 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define mp make_pair
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e4+5, MOD = 1e9+7, BASE = 31, MASK = (1 << 10) - 1;
int dp[MN][MN][2],sz[MN], k, x;
vector<pii> adj[MN]; ll iters;
void dfs (int cur, int par = -1) {
	memset(dp[cur],0x3f,sizeof dp[cur]); dp[cur][1][0] = dp[cur][1][1] = 0;
	for (pii p : adj[cur]) if (p.first != par) dfs(p.first,cur);
	++sz[cur];
	if (adj[cur].size() == 1 && cur != x) return;
	sort (all(adj[cur]),[&](pii a, pii b){return sz[a.first] > sz[b.first];});
	sz[cur] += sz[adj[cur][0].first];
	for (int i = 2; i <= sz[cur]; i++) dp[cur][i][0] = dp[adj[cur][0].first][i-1][0] + adj[cur][0].second * 2, dp[cur][i][1] = dp[adj[cur][0].first][i-1][1] + adj[cur][0].second;
	for (pii p : adj[cur]) if (p != adj[cur][0] && p.first != par) {
		sz[cur] += sz[p.first]; int sofar = min(sz[cur],k);
		for (int i = sofar; i >= 2; i--) {
			int ed = min(sz[p.first],i-1);
			for (int take = 1; take <= ed; take++) {
				dp[cur][i][0] = min(dp[cur][i][0],dp[cur][i-take][0] + dp[p.first][take][0] + p.second * 2);
				dp[cur][i][1] = min(dp[cur][i][1],dp[cur][i-take][1] + dp[p.first][take][0] + p.second * 2);
				dp[cur][i][1] = min(dp[cur][i][1],dp[cur][i-take][0] + dp[p.first][take][1] + p.second);
			}
		}
	}
}
int main () {
	int n;
	scanf ("%d %d %d",&n,&k,&x);
	for (int i = 1; i < n; i++) {
		int a,b,c;
		scanf ("%d %d %d",&a,&b,&c);
		adj[a].emplace_back(b,c); adj[b].emplace_back(a,c);
	}
	dfs(x);
	printf ("%d\n",dp[x][k][1]);
	return 0;
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d",&n,&k,&x);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
museum.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&a,&b,&c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2176 KB Output is correct
2 Correct 6 ms 2176 KB Output is correct
3 Correct 6 ms 2176 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2176 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 784376 KB Output is correct
2 Correct 401 ms 784248 KB Output is correct
3 Correct 460 ms 784692 KB Output is correct
4 Correct 415 ms 784376 KB Output is correct
5 Correct 433 ms 784376 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 784376 KB Output is correct
2 Correct 401 ms 784248 KB Output is correct
3 Correct 460 ms 784692 KB Output is correct
4 Correct 415 ms 784376 KB Output is correct
5 Correct 433 ms 784376 KB Output is correct
6 Correct 418 ms 784248 KB Output is correct
7 Correct 429 ms 784504 KB Output is correct
8 Correct 415 ms 784504 KB Output is correct
9 Correct 420 ms 784312 KB Output is correct
10 Correct 428 ms 784376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2176 KB Output is correct
2 Correct 6 ms 2176 KB Output is correct
3 Correct 6 ms 2176 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2176 KB Output is correct
6 Correct 473 ms 784376 KB Output is correct
7 Correct 401 ms 784248 KB Output is correct
8 Correct 460 ms 784692 KB Output is correct
9 Correct 415 ms 784376 KB Output is correct
10 Correct 433 ms 784376 KB Output is correct
11 Correct 418 ms 784248 KB Output is correct
12 Correct 429 ms 784504 KB Output is correct
13 Correct 415 ms 784504 KB Output is correct
14 Correct 420 ms 784312 KB Output is correct
15 Correct 428 ms 784376 KB Output is correct
16 Correct 455 ms 784376 KB Output is correct
17 Correct 514 ms 784248 KB Output is correct
18 Correct 445 ms 784480 KB Output is correct
19 Correct 443 ms 784376 KB Output is correct
20 Correct 449 ms 784376 KB Output is correct
21 Correct 553 ms 784632 KB Output is correct
22 Correct 553 ms 784252 KB Output is correct
23 Correct 624 ms 784376 KB Output is correct
24 Correct 546 ms 784376 KB Output is correct
25 Correct 573 ms 784760 KB Output is correct