oj.uz

Submission #1027715

# Submission time Handle Problem Language Result Execution time Memory
1027715 2024-07-19T09:25:42 Z vjudge1 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 336224 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5+5, V = 1e2+2;

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

int dfs(int f, int d, int nwV, int e) {
  if (dp[f][d][nwV][e] != -1) return dp[f][d][nwV][e];
  
  dp[f][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 (f && z == y) continue;
      
      int nwD = (edge[idx].first == z ? 0 : 1);
      dp[f][d][nwV][e] = max(dp[f][d][nwV][e], sum[x] - (!f ? 0 : a[y]) + dfs(1, nwD, nwV-1, idx));
    }
  }

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

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

  return dp[f][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][0][j][i] = dp[0][1][j][i] = dp[1][0][j][i] = dp[1][1][j][i] = -1;
    }
  }

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

  ans = 0;
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j <= v; j++) {
      ans = max({ans, dp[0][0][j][i], dp[0][1][j][i], dp[1][0][j][i], dp[1][1][j][i]});
    }
  }
  cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 7 ms 9048 KB Output is correct
8 Correct 3 ms 3932 KB Output is correct
9 Correct 14 ms 4016 KB Output is correct
10 Correct 5 ms 9048 KB Output is correct
11 Correct 5 ms 5288 KB Output is correct
12 Correct 3 ms 4184 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 336216 KB Output is correct
2 Correct 1237 ms 336224 KB Output is correct
3 Execution timed out 4066 ms 328892 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 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 7 ms 9048 KB Output is correct
8 Correct 3 ms 3932 KB Output is correct
9 Correct 14 ms 4016 KB Output is correct
10 Correct 5 ms 9048 KB Output is correct
11 Correct 5 ms 5288 KB Output is correct
12 Correct 3 ms 4184 KB Output is correct
13 Correct 1210 ms 336216 KB Output is correct
14 Correct 1237 ms 336224 KB Output is correct
15 Execution timed out 4066 ms 328892 KB Time limit exceeded
16 Halted 0 ms 0 KB -