oj.uz

Submission #873896

# Submission time Handle Problem Language Result Execution time Memory
873896 2023-11-16T02:35:27 Z noiaint Chase (CEOI17_chase) C++17
100 / 100
 266 ms 252680 KB 
#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
#define file "chase"
 
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
 
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
 
const int N = 1e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
 
template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}
 
int n, k;
vector<int> adj[N];
int a[N];
int f[N][105][2];
/*
f[u][i][0] : best value
f[u][i][1] : second-best value for rerooting
*/
int sum[N];
int tmp[N][105];
 
int res = 0;
 
void dfsF(int u, int p) {
    for (int v : adj[u]) if (v != p) {
        dfsF(v, u);
        for (int i = 1; i <= k; ++i) {
            int d = max(f[v][i][0], f[v][i - 1][0] + sum[v] - a[u]);
            if (d > f[u][i][0]) f[u][i][1] = f[u][i][0], f[u][i][0] = d;
            else maxi(f[u][i][1], d);
        }
    }
}
 
void dfsG(int u, int p) {
    for (int i = 1; i <= k; ++i) {
        maxi(res, f[u][i][0]);
        maxi(res, f[u][i - 1][0] + sum[u]);
    }
    for (int v : adj[u]) if (v != p) {
        // save changes
        for (int i = 1; i <= k; ++i) tmp[u][i] = f[u][i][0];
 
        // remove contribution
        for (int i = 1; i <= k; ++i) {
            int d = max(f[v][i][0], f[v][i - 1][0] + sum[v] - a[u]);
            if (f[u][i][0] == d) f[u][i][0] = f[u][i][1];            
        }
 
        // reroot
        for (int i = 1; i <= k; ++i) {
            int d = max(f[u][i][0], f[u][i - 1][0] + sum[u] - a[v]);
            if (d > f[v][i][0]) f[v][i][1] = f[v][i][0], f[v][i][0] = d;
            else maxi(f[v][i][1], d);
        }
        dfsG(v, u);
 
        // rollback changes
        for (int i = 1; i <= k; ++i) f[u][i][0] = tmp[u][i];
 
    }
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
 
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) sum[u] += a[v];
    }
    
    dfsF(1, 0);
    dfsG(1, 0);
 
    cout << res;
 
    return 0;
}
 
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
 
36
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 3 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 3 ms 8284 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 221268 KB Output is correct
2 Correct 237 ms 221008 KB Output is correct
3 Correct 145 ms 176752 KB Output is correct
4 Correct 134 ms 249936 KB Output is correct
5 Correct 266 ms 249744 KB Output is correct
6 Correct 259 ms 249808 KB Output is correct
7 Correct 254 ms 250640 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 3 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 3 ms 8284 KB Output is correct
13 Correct 241 ms 221268 KB Output is correct
14 Correct 237 ms 221008 KB Output is correct
15 Correct 145 ms 176752 KB Output is correct
16 Correct 134 ms 249936 KB Output is correct
17 Correct 266 ms 249744 KB Output is correct
18 Correct 259 ms 249808 KB Output is correct
19 Correct 254 ms 250640 KB Output is correct
20 Correct 256 ms 252680 KB Output is correct
21 Correct 34 ms 10916 KB Output is correct
22 Correct 259 ms 252496 KB Output is correct
23 Correct 135 ms 250452 KB Output is correct
24 Correct 256 ms 250708 KB Output is correct
25 Correct 136 ms 174344 KB Output is correct
26 Correct 259 ms 221304 KB Output is correct
27 Correct 217 ms 221264 KB Output is correct