oj.uz

Submission #1027759

# Submission time Handle Problem Language Result Execution time Memory
1027759 2024-07-19T09:42:56 Z d4xn Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 173648 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 100000, NN = 99999, V = 101;

int n, v, a[N];
ll ans, sum[N], dp[2][V][NN];
pair<int, int> edge[NN];
vector<pair<int, int>> adj[N];

ll dfs(int d, int nwV, int e) {
  if (dp[d][nwV][e] != -1) return dp[d][nwV][e];
  
  dp[d][nwV][e] = 0;

  int x = edge[e].first;
  int y = edge[e].second;
  if (d) swap(x, y);

  // estoy en x y vengo de y

  // lanzo pan
  if (nwV) {
    for (auto& [z, idx] : adj[x]) {
      if (z == y) continue;

      int nwD = (edge[idx].first == z ? 0 : 1);
      ll SEXO = sum[x] - a[y];
      dp[d][nwV][e] = max(dp[d][nwV][e], SEXO + dfs(nwD, nwV-1, idx));
    }
  }

  // no lanzo pan
  for (auto& [z, idx] : adj[x]) {
    if (z == y) continue;

    int nwD = (edge[idx].first == z ? 0 : 1);
    dp[d][nwV][e] = max(dp[d][nwV][e], dfs(nwD, nwV, idx));
  }

  return dp[d][nwV][e];
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  cin >> n >> v;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n-1; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    
    adj[x].push_back(make_pair(y, i));
    adj[y].push_back(make_pair(x, i));
  
    edge[i] = make_pair(x, y);
  }

  memset(sum, 0, sizeof(sum));
  for (int i = 0; i < n; i++) {
    for (auto& [j, idx] : adj[i]) {
      sum[i] += a[j];
    }
  }

  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j <= v; j++) {
      dp[0][j][i] = dp[1][j][i] = -1;
    }
  }

  ans = 0;
  for (int i = 0; i < n-1; i++) {
    ans = max(ans, dfs(0, v, i));
    ans = max(ans, dfs(1, v, i)); 
  }

  for (int i = 0; i < n; i++) {
    for (auto& [j, idx] : adj[i]) {
      int d = (edge[idx].first == j ? 0 : 1);
      ans = max(ans, sum[i] + dfs(d, v-1, idx));
    }
  }

  cout << ans << "\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Incorrect 1 ms 8792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Incorrect 1 ms 8792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 173564 KB Output is correct
2 Correct 841 ms 173648 KB Output is correct
3 Execution timed out 4027 ms 166596 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 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 3 ms 25180 KB Output is correct
5 Incorrect 1 ms 8792 KB Output isn't correct
6 Halted 0 ms 0 KB -