oj.uz

Submission #1027748

# Submission time Handle Problem Language Result Execution time Memory
1027748 2024-07-19T09:37:02 Z d4xn Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 334072 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 int long long

const int N = 100000, V = 101;

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);
      int SEXO = sum[x] - (!f ? 0 : a[y]);
      dp[f][d][nwV][e] = max(dp[f][d][nwV][e], SEXO + 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;
    }
  }

  /*if (n > 1000) {
    for (int i = 0; i < n-1; i++) {
      if (edge[i].first == 0) dfs(0, 0, v, i);
      if (edge[i].second == 0) dfs(0, 1, v, i); 
    }
  }
  else {*/
    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]});
    }
  }
  cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5464 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3420 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 1 ms 5464 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 12 ms 9052 KB Output is correct
8 Correct 2 ms 5720 KB Output is correct
9 Correct 13 ms 5900 KB Output is correct
10 Correct 5 ms 8796 KB Output is correct
11 Correct 3 ms 7008 KB Output is correct
12 Correct 3 ms 4188 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 334072 KB Output is correct
2 Correct 1172 ms 334068 KB Output is correct
3 Execution timed out 4066 ms 326716 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 5464 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3420 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 12 ms 9052 KB Output is correct
8 Correct 2 ms 5720 KB Output is correct
9 Correct 13 ms 5900 KB Output is correct
10 Correct 5 ms 8796 KB Output is correct
11 Correct 3 ms 7008 KB Output is correct
12 Correct 3 ms 4188 KB Output is correct
13 Correct 1129 ms 334072 KB Output is correct
14 Correct 1172 ms 334068 KB Output is correct
15 Execution timed out 4066 ms 326716 KB Time limit exceeded
16 Halted 0 ms 0 KB -