oj.uz

Submission #1052497

# Submission time Handle Problem Language Result Execution time Memory
1052497 2024-08-10T15:17:00 Z TAhmed33 Chase (CEOI17_chase) C++
0 / 100
 682 ms 176432 KB 

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e5 + 25;
    ll dp[MAXN][101], p[MAXN], ans[MAXN], s[MAXN];
    ll dp2[MAXN][101];
    vector <int> adj[MAXN];
    int n, v; 
    ll mx = 0;
    void dfs (int pos, int par) {
    	for (auto j : adj[pos]) {
    		if (j != par) {
    			dfs(j, pos);
    		}
    	}
    	vector <pair <ll, ll>> ii[v + 1];
    	vector <pair <ll, ll>> ii2[v + 1];
    	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
    	ii[0].push_back({0, 0}); ii2[0].push_back({0, 0});
    	for (int i = 1; i <= v; i++) {
    		dp[pos][i] = 0; dp2[pos][i] = 0;
    		for (auto j : adj[pos]) {
    			if (j != par) {
    				ll x = max(dp[j][i], dp[j][i - 1] + s[j] - p[pos]);
    				dp[pos][i] = max(dp[pos][i], x);
    				ii[i].push_back({x, j});
    				x = max(dp2[j][i], dp2[j][i - 1] + s[pos] - p[j]);
    				dp2[pos][i] = max(dp2[pos][i], x);
    				ii2[i].push_back({x, j});
    			}
    		}
    		dp2[pos][i] = max(dp2[pos][i], s[pos]);
    		ii2[i].push_back({s[pos], 0});
    	}
    	for (int i = 1; i <= v; i++) {
    		sort(ii[i].begin(), ii[i].end());
    		sort(ii2[i].begin(), ii2[i].end());
    	}
    	for (int i = 0; i <= v; i++) {
    		for (auto j : adj[pos]) {
    			if (j == par) continue;
    			if (j == ii[i].back().second) {
    				mx = max(mx, ii[i][int(ii[i].size()) - 2].first + dp2[j][v - i]);
    			} else {
    				mx = max(mx, dp[pos][i] + dp2[j][v - i]);
    			}
    		}
    	}
    }
    void solve () {
    	cin >> n >> v;
      if (v == 0) {
cout << 0 << '\n'; return;}
    	for (int i = 1; i <= n; i++) {
    		cin >> p[i];
    	}
    	for (int i = 1; i < n; i++) {
    		int a, b; cin >> a >> b;
    		adj[a].push_back(b);
    		adj[b].push_back(a);
    		s[a] += p[b]; s[b] += p[a];
    	}
    	dfs(1, -1);
    	cout << mx << '\n';
    }		
    signed main () {
    	ios::sync_with_stdio(0); cin.tie(0);
    	int tc = 1; //cin >> tc;
    	while (tc--) solve();
    }

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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