oj.uz

Submission #987674

# Submission time Handle Problem Language Result Execution time Memory
987674 2024-05-23T10:43:13 Z ErJ Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 182904 KB 
#include<bits/stdc++.h>

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define inf 1000000000000000
#define rep(i,n) for(int i = 0; i < n; i++)


using namespace std;

vi val;

struct edge{
    ll from;
    ll to;
    vi dp;
    bool ready = false;
};

vector<vector<edge>> edges;

void readyEdge(edge &e){
    ll sum = 0;
    for(int i = 0; i < edges[e.to].size(); i++){
        ll v = edges[e.to][i].to;
        if(v != e.from){
            sum += val[v];
            if(!edges[e.to][i].ready){
                readyEdge(edges[e.to][i]);
            }
        }
    }
    for(int i = 1; i < e.dp.size(); i++){
        ll MAX1 = 0, MAX2 = 0;
        for(int j = 0; j < edges[e.to].size(); j++){
            ll v = edges[e.to][j].to;
            if(v != e.from){
                MAX1 = max(MAX1, edges[e.to][j].dp[i-1]);
                MAX2 = max(MAX2, edges[e.to][j].dp[i]);
            }
        }
        e.dp[i] = max(MAX1 + sum, MAX2);
    }
    e.ready = true;
}


int main(){
    ll n, v;
    cin >> n >> v;
    val.resize(n, 0);
    rep(i,n){
        cin >> val[i];
    }
    edges.resize(n);
    rep(i, n-1){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        edge e, e1;
        e.from = a;
        e.to = b;
        e.dp.resize(v + 1, 0);
        e1.from = b;
        e1.to = a;
        e1.dp.resize(v + 1, 0);
        edges[a].push_back(e);
        edges[b].push_back(e1);
    }
    rep(i, n){
        rep(j, edges[i].size()){
            if(!edges[i][j].ready){
                readyEdge(edges[i][j]);
            }
        }
    }
    ll ans = 0;
    rep(i, n){
        ll sum = 0;
        ll MAXV = 0, MAXV1 = 0;
        rep(j, edges[i].size()){
            sum += val[edges[i][j].to];
            MAXV = max(MAXV, edges[i][j].dp[v]);
            MAXV1 = max(MAXV1, edges[i][j].dp[v - 1]);
        }
        ans = max(ans, max(sum + MAXV1, MAXV));
    }
    cout << ans << endl;
}

Compilation message

chase.cpp: In function 'void readyEdge(edge&)':
chase.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < edges[e.to].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 1; i < e.dp.size(); i++){
      |                    ~~^~~~~~~~~~~~~
chase.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0; j < edges[e.to].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
   73 |         rep(j, edges[i].size()){
      |             ~~~~~~~~~~~~~~~~~~     
chase.cpp:73:9: note: in expansion of macro 'rep'
   73 |         rep(j, edges[i].size()){
      |         ^~~
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
   83 |         rep(j, edges[i].size()){
      |             ~~~~~~~~~~~~~~~~~~     
chase.cpp:83:9: note: in expansion of macro 'rep'
   83 |         rep(j, edges[i].size()){
      |         ^~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 182868 KB Output is correct
2 Correct 495 ms 182904 KB Output is correct
3 Execution timed out 4051 ms 176212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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