oj.uz

Submission #35823

# Submission time Handle Problem Language Result Execution time Memory
35823 2017-12-01T05:07:19 Z funcsr Chase (CEOI17_chase) C++14
70 / 100
 389 ms 93068 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline void chmax(long long &x, long long v) { if (x < v) x = v; }

int N, K;
int A[100000];
long long T[100000];
vector<int> G[100000];
int U[100000], R[100000];
void dfs(int x, int p, int r) {
  U[x] = p;
  R[x] = r;
  for (int t : G[x]) {
    if (t == p) continue;
    dfs(t, x, r+1);
  }
}

long long dp[100000][101];
void f(int x, int p) {
  for (int t : G[x]) {
    if (t == p) continue;
    f(t, x);
    rep(k, K+1) chmax(dp[x][k], dp[t][k]);
    rep(k, K) chmax(dp[x][k+1], dp[t][k]+T[x]);
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K;
  rep(i, N) cin >> A[i];
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  rep(i, N) for (int t : G[i]) T[i] += A[t];

  long long m = 0;
  rep(i, N) {
    if (N > 1000 && i > 0) continue;
    dfs(i, -1, 0);
    rep(i, N) if (U[i] != -1) T[i] -= A[U[i]];
    rep(i, N) rep(j, K+1) dp[i][j] = 0;
    f(i, -1);
    m = max(m, dp[i][K]);
    rep(i, N) if (U[i] != -1) T[i] += A[U[i]];
  }
  cout << m << "\n";
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 85376 KB Output is correct
2 Correct 0 ms 85376 KB Output is correct
3 Correct 0 ms 85376 KB Output is correct
4 Correct 0 ms 85376 KB Output is correct
5 Correct 0 ms 85376 KB Output is correct
6 Correct 0 ms 85376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 85376 KB Output is correct
2 Correct 0 ms 85376 KB Output is correct
3 Correct 0 ms 85376 KB Output is correct
4 Correct 0 ms 85376 KB Output is correct
5 Correct 0 ms 85376 KB Output is correct
6 Correct 0 ms 85376 KB Output is correct
7 Correct 379 ms 85376 KB Output is correct
8 Correct 96 ms 85376 KB Output is correct
9 Correct 43 ms 85376 KB Output is correct
10 Correct 389 ms 85376 KB Output is correct
11 Correct 179 ms 85376 KB Output is correct
12 Correct 93 ms 85376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 93068 KB Output is correct
2 Correct 156 ms 93044 KB Output is correct
3 Correct 83 ms 88928 KB Output is correct
4 Correct 103 ms 88544 KB Output is correct
5 Correct 163 ms 88544 KB Output is correct
6 Correct 153 ms 88544 KB Output is correct
7 Correct 139 ms 88544 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 85376 KB Output is correct
2 Correct 0 ms 85376 KB Output is correct
3 Correct 0 ms 85376 KB Output is correct
4 Correct 0 ms 85376 KB Output is correct
5 Correct 0 ms 85376 KB Output is correct
6 Correct 0 ms 85376 KB Output is correct
7 Correct 379 ms 85376 KB Output is correct
8 Correct 96 ms 85376 KB Output is correct
9 Correct 43 ms 85376 KB Output is correct
10 Correct 389 ms 85376 KB Output is correct
11 Correct 179 ms 85376 KB Output is correct
12 Correct 93 ms 85376 KB Output is correct
13 Correct 146 ms 93068 KB Output is correct
14 Correct 156 ms 93044 KB Output is correct
15 Correct 83 ms 88928 KB Output is correct
16 Correct 103 ms 88544 KB Output is correct
17 Correct 163 ms 88544 KB Output is correct
18 Correct 153 ms 88544 KB Output is correct
19 Correct 139 ms 88544 KB Output is correct
20 Incorrect 159 ms 88544 KB Output isn't correct
21 Halted 0 ms 0 KB -