oj.uz

Submission #939763

# Submission time Handle Problem Language Result Execution time Memory
939763 2024-03-06T17:44:52 Z iskhakkutbilim Chase (CEOI17_chase) C++17
70 / 100
 644 ms 92824 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
 
using i64 = long long;
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k; cin >> n >> k;
    vector <int> a(n);
    for ( auto &u: a ) cin >> u;
    vector <vector<int>> G(n);
    for ( int i = 0; i + 1 < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb(v), G[v].pb(u);
    }
    if ( !k ){ return cout << "0\n", 0; }
    const int inf = 1e15;
    auto opt = [&](int rt){
        vector <vector<int>> dp(n, vector <int> (k + 1));
        vector <int> s(n);
        auto dfs2 = [&](auto dfs2, int u, int p) -> void{
			for ( auto &v: G[u] ){
				if ( v != p ){
					s[u] += a[v];
					dfs2(dfs2, v, u);
				}
			}
		};
		dfs2(dfs2, rt, -1);
        auto dfs = [&](auto dfs, int u, int p) -> void{
            for ( auto &v: G[u] ){
                if ( v == p ) continue;
                for ( int j = 0; j <= k; j++ ){
					chmax(dp[v][j], dp[u][j]);
					if ( j > 0 ){
						chmax(dp[v][j], dp[u][j - 1] + s[v]);
					}
                }
                dfs(dfs, v, u);
            }
        };
        dp[rt][1] = s[rt];
        dfs(dfs, rt, -1);
        int ret = 0;
        for ( int i = 0; i < n; i++ ){
            for ( int j = 0; j <= k; j++ ){
				chmax(ret, dp[i][j]);
            }
        }
        return ret;
    };
    int ans = 0;
    for ( int i = 0; i < n; i++ ){
        chmax(ans, opt(i));
        if ( n > 1e3 ) break;
    }
    cout << ans;
 
    cout << '\n';
}
 
/*
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
*/

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:45:15: warning: unused variable 'inf' [-Wunused-variable]
   45 |     const int inf = 1e15;
      |               ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 616 ms 1368 KB Output is correct
8 Correct 65 ms 604 KB Output is correct
9 Correct 57 ms 600 KB Output is correct
10 Correct 644 ms 1344 KB Output is correct
11 Correct 216 ms 1260 KB Output is correct
12 Correct 109 ms 620 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 92824 KB Output is correct
2 Correct 137 ms 92752 KB Output is correct
3 Correct 99 ms 90236 KB Output is correct
4 Correct 54 ms 13392 KB Output is correct
5 Correct 147 ms 90296 KB Output is correct
6 Correct 149 ms 90308 KB Output is correct
7 Correct 151 ms 90060 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 616 ms 1368 KB Output is correct
8 Correct 65 ms 604 KB Output is correct
9 Correct 57 ms 600 KB Output is correct
10 Correct 644 ms 1344 KB Output is correct
11 Correct 216 ms 1260 KB Output is correct
12 Correct 109 ms 620 KB Output is correct
13 Correct 136 ms 92824 KB Output is correct
14 Correct 137 ms 92752 KB Output is correct
15 Correct 99 ms 90236 KB Output is correct
16 Correct 54 ms 13392 KB Output is correct
17 Correct 147 ms 90296 KB Output is correct
18 Correct 149 ms 90308 KB Output is correct
19 Correct 151 ms 90060 KB Output is correct
20 Incorrect 150 ms 90300 KB Output isn't correct
21 Halted 0 ms 0 KB -