oj.uz

Submission #143305

# Submission time Handle Problem Language Result Execution time Memory
143305 2019-08-13T15:26:20 Z Milki Chase (CEOI17_chase) C++14
100 / 100
 1469 ms 336684 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
#define int long long

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, MAXN - 1);
    b = point(0, MAXN - 1);
  }
  void ubaci(point x){
    if(x.first > a.first){
      if(x.second != a.second)
        b = a;

      a = x;
    }
    else if(x.first > b.first){
      if(x.second != a.second)
        b = x;
    }
  }
  void ubacic(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);

  dp_up[1][x] = sum[x];
  mx1[1].ubaci( {sum[x], -1} );

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

    dfs(e, x);
    FOR(i, 1, k + 1){
      ll ans = dp_down[i - 1][e] + sum[e] - val[x];
      ans = max(ans, dp_down[i][e]);

      if(ans > dp_down[i][x]){
        dp_down[i][x] = ans;
      }
      mx2[i].ubaci(point(ans, e));

      dp_down[i][x] = max(dp_down[i][x], dp_down[i - 1][x]);

      ans = dp_up[i - 1][e] + sum[x] - val[e];
      ans = max(ans, dp_up[i][e]);

      if(ans > dp_up[i][x]){
        dp_up[i][x] = ans;
      }
      mx1[i].ubacic(point(ans, e));

      dp_up[i][x] = max(dp_up[i][x], dp_up[i - 1][x]);

      mx1[i].ubaci(mx1[i - 1].a);
      mx1[i].ubaci(mx1[i - 1].b);

      mx2[i].ubaci(mx2[i - 1].a);
      mx2[i].ubaci(mx2[i - 1].b);
    }
  }

  REP(i, k + 1){
    //TRACE(mx1[i].a.first); TRACE(mx2[k - i].a.first);
    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);
    }
  }

}

signed 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);
  }

  if(k == 0){
    cout << 0;
    return 0;
  }

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

  dfs(0);

  cout << sol;
}

Subtask #1
20.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 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 35 ms 2680 KB Output is correct

Subtask #2
20.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 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 35 ms 2680 KB Output is correct
7 Correct 14 ms 7160 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 11 ms 5496 KB Output is correct
11 Correct 7 ms 3576 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 332028 KB Output is correct
2 Correct 1063 ms 332244 KB Output is correct
3 Correct 322 ms 12996 KB Output is correct
4 Correct 112 ms 11896 KB Output is correct
5 Correct 1205 ms 165660 KB Output is correct
6 Correct 1469 ms 167124 KB Output is correct
7 Correct 1374 ms 166848 KB Output is correct

Subtask #4
30.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 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 35 ms 2680 KB Output is correct
7 Correct 14 ms 7160 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 11 ms 5496 KB Output is correct
11 Correct 7 ms 3576 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 1066 ms 332028 KB Output is correct
14 Correct 1063 ms 332244 KB Output is correct
15 Correct 322 ms 12996 KB Output is correct
16 Correct 112 ms 11896 KB Output is correct
17 Correct 1205 ms 165660 KB Output is correct
18 Correct 1469 ms 167124 KB Output is correct
19 Correct 1374 ms 166848 KB Output is correct
20 Correct 1262 ms 167092 KB Output is correct
21 Correct 67 ms 9336 KB Output is correct
22 Correct 1207 ms 167048 KB Output is correct
23 Correct 111 ms 11640 KB Output is correct
24 Correct 1197 ms 167012 KB Output is correct
25 Correct 306 ms 11844 KB Output is correct
26 Correct 1111 ms 336684 KB Output is correct
27 Correct 1088 ms 336608 KB Output is correct