oj.uz

Submission #583293

# Submission time Handle Problem Language Result Execution time Memory
583293 2022-06-25T08:15:36 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 264524 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++) {
        for (int j = 0; i + j <= bread_have; j++) {
          sol = max(sol, dp1[b][i] + dp2[c][j]);
        }
      }
      /// yes a
      for (int i = 0; i <= bread_have; i++) {
        for (int j = 0; i + j + 1 <= bread_have; j++) {
          sol = max(sol, dp1[b][i] + dp2[c][j] + (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 1 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 1 ms 2644 KB Output is correct
5 Correct 2 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 1 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 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 21 ms 5332 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 52 ms 5204 KB Output is correct
10 Correct 37 ms 5204 KB Output is correct
11 Correct 7 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 1988 ms 264524 KB Output is correct
2 Correct 2019 ms 264480 KB Output is correct
3 Execution timed out 4112 ms 258624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 21 ms 5332 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 52 ms 5204 KB Output is correct
10 Correct 37 ms 5204 KB Output is correct
11 Correct 7 ms 5204 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 1988 ms 264524 KB Output is correct
14 Correct 2019 ms 264480 KB Output is correct
15 Execution timed out 4112 ms 258624 KB Time limit exceeded
16 Halted 0 ms 0 KB -