oj.uz

Submission #1027728

# Submission time Handle Problem Language Result Execution time Memory
1027728 2024-07-19T09:30:24 Z vjudge1 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);
      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;
    }
  }

  /*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], 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 7512 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 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 2 ms 7512 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 8 ms 9048 KB Output is correct
8 Correct 3 ms 3928 KB Output is correct
9 Correct 14 ms 4004 KB Output is correct
10 Correct 6 ms 8792 KB Output is correct
11 Correct 5 ms 5212 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 1221 ms 334068 KB Output is correct
2 Correct 1202 ms 334072 KB Output is correct
3 Execution timed out 4056 ms 326844 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 7512 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 8 ms 9048 KB Output is correct
8 Correct 3 ms 3928 KB Output is correct
9 Correct 14 ms 4004 KB Output is correct
10 Correct 6 ms 8792 KB Output is correct
11 Correct 5 ms 5212 KB Output is correct
12 Correct 3 ms 4184 KB Output is correct
13 Correct 1221 ms 334068 KB Output is correct
14 Correct 1202 ms 334072 KB Output is correct
15 Execution timed out 4056 ms 326844 KB Time limit exceeded
16 Halted 0 ms 0 KB -