oj.uz

Submission #583295

# Submission time Handle Problem Language Result Execution time Memory
583295 2022-06-25T08:17:25 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 263760 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int B = 100 + 7;
const ll INF = (ll) 1e18 + 7;
int n, bread_have, pigs[N];
vector<int> g[N];
ll sum_vecs[N];
ll dp1[N][B];
ll dp2[N][B];
ll dp3[N][B];
ll sol;

void dfs1(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs1(b, a);
    }
  }
  for (int i = 0; i <= bread_have; i++) {
    if (i >= 1) {
      dp1[a][i] = max(dp1[a][i], sum_vecs[a]);
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp1[a][i] = max(dp1[a][i], dp1[b][i]);
      if (i >= 1) {
        dp1[a][i] = max(dp1[a][i], dp1[b][i - 1] + (sum_vecs[a] - pigs[b]));
      }
    }
  }
}

void dfs2(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs2(b, a);
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp2[a][i] = max(dp2[a][i], dp2[b][i]);
      if (i >= 1) {
        dp2[a][i] = max(dp2[a][i], dp2[b][i - 1] + (sum_vecs[a] - pigs[p]));
      }
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp3[a][i] = max(dp3[a][i], dp2[b][i]);
      if (i >= 1) {
        dp3[a][i] = max(dp3[a][i], dp2[b][i - 1] + sum_vecs[a]);
      }
    }
  }
}

/// sol = max(sol, sum_vecs[a]);

void dfs3(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs3(b, a);
    }
  }
  sol = max(sol, sum_vecs[a]);
  sol = max(sol, dp1[a][bread_have]);
  sol = max(sol, dp2[a][bread_have]);
  sol = max(sol, dp3[a][bread_have]);

  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (auto &c : g[a]) {
      if (c == p) {
        continue;
      }
      if (b == c) {
        continue;
      }
      /// no a
      for (int i = 0; i <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + dp2[c][bread_have - i]);

      }
      /// yes a
      for (int i = 0; i + 1 <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + dp2[c][bread_have - i - 1] + (sum_vecs[a] - pigs[b]));
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  ///freopen ("input.txt", "r", stdin);

  cin >> n >> bread_have;

  for (int i = 1; i <= n; i++) {
    cin >> pigs[i];
  }

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    sum_vecs[a] += pigs[b];
    sum_vecs[b] += pigs[a];
  }
  if (bread_have == 0) {
    cout << "0\n";
    return 0;
  }
  ll Max = 0;
  for (int root = 1; root <= n; root++) {
    root = 1;
    for (int i = 0; i <= n + 1; i++) {
      for (int j = 0; j <= bread_have + 1; j++) {
        dp1[i][j] = 0;
        dp2[i][j] = 0;
        dp3[i][j] = 0;
      }
    }
    sol = -INF;
    dfs1(root);
    dfs2(root);
    dfs3(root);
    cout << sol << "\n";
    exit(0);
    cout << root << " ---> " << sol << "\n";
    Max = max(Max, sol);

    //exit(0);
  }

  cout << "\t\t\t\t Max = " << Max << "\n";

  assert(Max <= 36);

  return 0;


  /*ll sol = -INF;
  for (int root = 1; root <= n; root++) {
    dfs_down(root);
    dfs_up(root);
   /// sol = max(sol, from_up[root][bread_have]);


    exit(0);
  }
  cout << sol << "\n";*/
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 19 ms 5268 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 263716 KB Output is correct
2 Correct 350 ms 263760 KB Output is correct
3 Execution timed out 4097 ms 258528 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 19 ms 5268 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 342 ms 263716 KB Output is correct
14 Correct 350 ms 263760 KB Output is correct
15 Execution timed out 4097 ms 258528 KB Time limit exceeded
16 Halted 0 ms 0 KB -