oj.uz

Submission #101412

# Submission time Handle Problem Language Result Execution time Memory
101412 2019-03-19T01:16:08 Z dwsc Chase (CEOI17_chase) C++14
70 / 100
 2362 ms 99188 KB 
#include <bits/stdc++.h>
using namespace std;
int n,v;
int p[100010];
vector<int> adj[100010];
long long memo[100010][110];
long long dp(int x,int dist,int pa){
    if (dist == -1) return -1e18;
    if (memo[x][dist] != -1) return memo[x][dist];
   // cout << x << " " << dist << " " << pa << '\n';
    long long ans = 0;
    long long sum = 0;
    for (int i = 0; i < (int)(adj[x].size()); i++){
        int nx = adj[x][i];
        if (nx == pa) continue;
        sum += p[nx];
    }
   // cout << sum << "\n";
    for (int i = 0; i < (int)(adj[x].size()); i++){
        int nx = adj[x][i];
        if (nx == pa) continue;
        ans = max(ans,dp(nx,dist-1,x)+sum);
        ans = max(ans,dp(nx,dist,x));
    }
    return memo[x][dist] = ans;
}
int main(){
    cin >> n >> v;
    for (int i = 0; i < n; i++){
        cin >> p[i];
    }
    for (int i = 0; i < n-1; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if (n <= 1000){
        long long ans = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k <= v; k++) memo[j][k] = -1;
            }
          //  cout << dp(i,v,-1) << "\n";
            ans = max(ans,dp(i,v,-1));
        }
        cout << ans;
    }
    else{
        for (int j = 0; j < n; j++){
            for (int k = 0; k <= v; k++) memo[j][k] = -1;
        }
        cout << dp(0,v,-1);
    }
}
/*
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
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2660 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 1819 ms 3660 KB Output is correct
8 Correct 152 ms 3704 KB Output is correct
9 Correct 47 ms 3584 KB Output is correct
10 Correct 305 ms 3748 KB Output is correct
11 Correct 272 ms 3680 KB Output is correct
12 Correct 250 ms 3704 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2206 ms 97164 KB Output is correct
2 Correct 2362 ms 99188 KB Output is correct
3 Correct 198 ms 94896 KB Output is correct
4 Correct 238 ms 94456 KB Output is correct
5 Correct 803 ms 94432 KB Output is correct
6 Correct 689 ms 94620 KB Output is correct
7 Correct 804 ms 94568 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2660 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 1819 ms 3660 KB Output is correct
8 Correct 152 ms 3704 KB Output is correct
9 Correct 47 ms 3584 KB Output is correct
10 Correct 305 ms 3748 KB Output is correct
11 Correct 272 ms 3680 KB Output is correct
12 Correct 250 ms 3704 KB Output is correct
13 Correct 2206 ms 97164 KB Output is correct
14 Correct 2362 ms 99188 KB Output is correct
15 Correct 198 ms 94896 KB Output is correct
16 Correct 238 ms 94456 KB Output is correct
17 Correct 803 ms 94432 KB Output is correct
18 Correct 689 ms 94620 KB Output is correct
19 Correct 804 ms 94568 KB Output is correct
20 Incorrect 334 ms 94568 KB Output isn't correct
21 Halted 0 ms 0 KB -