oj.uz

Submission #850501

# Submission time Handle Problem Language Result Execution time Memory
850501 2023-09-16T17:55:04 Z Benmath Chase (CEOI17_chase) C++14
40 / 100
 329 ms 2148 KB 
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;
int n;
int v;
long long int p[1010];
vector<int> adjl[1010];
int vis[1010];
long long int dpnula[1010][105];
long long int dp[1010][105];
void dfs(int s){
    vis[s]++;
    long long int suma = 0;
    for (int i = 0;i< adjl[s].size(); i++){
        if(vis[adjl[s][i]] == 0){
    
            suma = suma + p[adjl[s][i]];
        }
    }

    for (int i = 0;i < adjl[s].size(); i++){
        if (vis[adjl[s][i]] == 0){
            dfs(adjl[s][i]);
            for (int j = 1; j <=v; j++){
                dpnula[s][j] = max(dpnula[s][j], dpnula[adjl[s][i]][j-1] + suma);
                dpnula[s][j] = max(dpnula[s][j], dp[adjl[s][i]][j]);
                dp[s][j] = max(dp[s][j], dpnula[adjl[s][i]][j-1] + suma);
                dp[s][j] = max(dp[s][j], dp[adjl[s][i]][j]);
            }
        }
    } 
    
}
int main(){
    cin >> n;
    cin >> v;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    for(int i = 0; i < (n-1); i++){
        int a, b;
        cin >> a >> b;
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }
    dfs(1);
    long long int ans = 0;
    for(int i = 1; i<=n; i++){
        for (int k = 1; k<=n; k++){
            for(int t = 0; t<=v; t++){
                dpnula[k][t] = 0;
                dp[k][t] = 0;
            }
            vis[k] = 0;
        }
        dfs(i);
        ans = max(ans, dp[i][v]);
    }
    cout << ans;
}

Compilation message

chase.cpp: In function 'void dfs(int)':
chase.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0;i< adjl[s].size(); i++){
      |                    ~^~~~~~~~~~~~~~~~
chase.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0;i < adjl[s].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 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 348 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 314 ms 2140 KB Output is correct
8 Correct 36 ms 2140 KB Output is correct
9 Correct 30 ms 2140 KB Output is correct
10 Correct 329 ms 2148 KB Output is correct
11 Correct 120 ms 2148 KB Output is correct
12 Correct 47 ms 2140 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 314 ms 2140 KB Output is correct
8 Correct 36 ms 2140 KB Output is correct
9 Correct 30 ms 2140 KB Output is correct
10 Correct 329 ms 2148 KB Output is correct
11 Correct 120 ms 2148 KB Output is correct
12 Correct 47 ms 2140 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -