Submission #155711

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
155711	2019-09-30 03:26:57	Fischer	Museum (CEOI17_museum)	C++14	80 / 100	3085 ms	784760 KiB

museum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 2;
struct Node {
  int v, w;
};
vector<Node> g[maxn];
int n, k, x;
int sz[maxn];
int memo[maxn][maxn][2];
void dfs(int x, int p) {
  sz[x] = 1;
  for (auto node : g[x]) {
    if (node.v == p) continue;
    dfs(node.v, x);
    sz[x] += sz[node.v];
  }
  memo[x][1][0] = memo[x][1][1] = 0; 
  for (auto node : g[x]) {
    if (node.v == p) continue;
    for (int i = min(sz[x], k); i >= 2; --i) {
      for (int j = min(sz[node.v], i-1); j >= 1; --j) {
        memo[x][i][1] = min(memo[x][i][1],
          min(
            memo[x][i-j][1] + memo[node.v][j][0] + (node.w<<1),
            memo[x][i-j][0] + memo[node.v][j][1] + node.w
          ));
        memo[x][i][0] = min(memo[x][i][0], 
          memo[x][i-j][0] + memo[node.v][j][0] + (node.w<<1));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 20