oj.uz

Submission #143035

# Submission time Handle Problem Language Result Execution time Memory
143035 2019-08-12T16:32:11 Z Milki Chase (CEOI17_chase) C++14
0 / 100
 1000 ms 332676 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<ll, ll> point;

const int MAXN = 1e5 + 5, MAXV = 105;
const ll inf = 1e16;

int n, k, val[MAXN];
vector <int> E[MAXN];
ll dp_down[MAXV][MAXN], sum[MAXN], sol, dp_up[MAXV][MAXN];

struct Best{
  point a, b;
  Best(){
    a = point(0, -1);
    b = point(0, -2);
  }
  void ubaci(point x){
    if(x.first > a.first){
      b = a;
      a = x;
    }
    else if(x.first > b.first){
      b = x;
    }
  }
};

void dfs(int x, int p = -1){
  vector<Best> mx1, mx2;
  mx1.resize(k + 1); mx2.resize(k + 1);

  for(auto e : E[x]){
    if(e == p) continue;

    dfs(e, x);
    FOR(i, 1, k + 1){
      dp_down[i][x] = max(dp_down[i - 1][e] + sum[e] - val[x], dp_down[i][e] );
      dp_down[i][x] = max(dp_down[i][x], dp_down[i - 1][x]);
      if(i > 1){
        dp_up[i][x] = max(dp_up[i - 1][e] + sum[x] - val[e], dp_up[i][e] );
        dp_up[i][x] = max(dp_up[i][x], dp_up[i - 1][x]);
      }
      else{
        dp_up[i][x] = sum[x];
      }
      mx1[i].ubaci(point(dp_up[i][x], e));
      mx2[i].ubaci(point(dp_down[i][x], e));

      sol = max(sol, dp_down[i][x]);
      sol = max(sol, dp_up[i][x]);
    }
  }

  REP(i, k + 1){
    if(mx1[i].a.second == mx2[k - i].a.second){
      sol = max(sol, mx1[i].a.first + mx2[k - i].b.first);
      sol = max(sol, mx1[i].b.first + mx2[k - i].a.first);
    }
    else{
      sol = max(sol, mx1[i].a.first + mx2[k - i].a.first);
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> k;
  REP(i, n)
    cin >> val[i];
  REP(i, n - 1){
    int a, b; cin >> a >> b; a --; b --;
    E[a].pb(b); E[b].pb(a);
  }

  REP(i, n){
    for(auto e : E[i])
      sum[i] += val[e];
    sol = max(sol, sum[i]);
  }
  dfs(0);

  cout << sol;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1000 ms 332676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -