Submission #987709

#	Time	Username	Problem	Language	Result	Execution time	Memory
987709		ErJ	Chase (CEOI17_chase)	C++17	40 / 100	4027 ms	350532 KiB

chase

#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;

struct node{
    ll id;
    vi dp1;
    vi dp2;
    ll sum = 0;
    bool ready = false;
};

vector<node> nodes;

vi val;

struct edge{
    ll from;
    ll to;
    vi dp;
    bool ready = false;
    ll anti = -1; //index anti edge v e.to FUJ
};

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;
}

void readyNode(int u){
    rep(i, edges[u].size()){
        ll v = edges[u][i].to;
        nodes[u].sum += val[v];
        rep(j, nodes[u].dp1.size()){
            if(edges[u][i].dp[j] >= nodes[u].dp1[j]){
                nodes[u].dp2[j] = nodes[u].dp1[j];
                nodes[u].dp1[j] = edges[u][i].dp[j];
            }else{
                if(edges[u][i].dp[j] > nodes[u].dp2[j]){
                    nodes[u].dp2[j] = edges[u][i].dp[j];
                }
            }
        }      
    }
    nodes[u].ready = true;
}

void readyEdge2(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){
                readyEdge2(edges[e.to][i]);
            }
        }
    }
    if(!nodes[e.to].ready){
        readyNode(e.to);
    }
    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]);
            }
        }*/
        MAX1 = nodes[e.to].dp1[i- 1];
        if(edges[e.to][e.anti].dp[i - 1] == nodes[e.to].dp1[i - 1]){
            MAX1 = nodes[e.to].dp2[i - 1];
        }
        MAX2 = nodes[e.to].dp1[i];
        if(edges[e.to][e.anti].dp[i] == nodes[e.to].dp1[i]){
            MAX2 = nodes[e.to].dp2[i];
        }
        e.dp[i] = max(MAX1 + (nodes[e.to].sum - val[e.from]), MAX2);
    }
    e.ready = true;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n, v;
    cin >> n >> v;
    val.resize(n, 0);
    rep(i,n){
        cin >> val[i];
        node no;
        no.dp1.resize(v + 1, 0);
        no.dp2.resize(v + 1, 0);
        no.id = i;
        no.ready = false;
        no.sum = 0;
        nodes.push_back(no);
    }
    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);
        e.anti = edges[b].size();
        e1.anti = edges[a].size();
        edges[a].push_back(e);
        edges[b].push_back(e1);
    }
    if(v == 0){
        cout << 0 << endl;
        return 0;
    }
    rep(i, n){
        rep(j, edges[i].size()){
            if(!edges[i][j].ready){
                if(i == 0){
                    readyEdge(edges[i][j]);
                }else{            
                    readyEdge2(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 (stderr)

chase.cpp: In function 'void readyEdge(edge&)':
chase.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < edges[e.to].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 1; i < e.dp.size(); i++){
      |                    ~~^~~~~~~~~~~~~
chase.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 0; j < edges[e.to].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp: In function 'void readyNode(int)':
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++)
......
   61 |     rep(i, edges[u].size()){
      |         ~~~~~~~~~~~~~~~~~~         
chase.cpp:61:5: note: in expansion of macro 'rep'
   61 |     rep(i, edges[u].size()){
      |     ^~~
chase.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,n) for(int i = 0; i < n; i++)
......
   64 |         rep(j, nodes[u].dp1.size()){
      |             ~~~~~~~~~~~~~~~~~~~~~~ 
chase.cpp:64:9: note: in expansion of macro 'rep'
   64 |         rep(j, nodes[u].dp1.size()){
      |         ^~~
chase.cpp: In function 'void readyEdge2(edge&)':
chase.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < edges[e.to].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 1; i < e.dp.size(); i++){
      |                    ~~^~~~~~~~~~~~~
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++)
......
  152 |         rep(j, edges[i].size()){
      |             ~~~~~~~~~~~~~~~~~~     
chase.cpp:152:9: note: in expansion of macro 'rep'
  152 |         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++)
......
  166 |         rep(j, edges[i].size()){
      |             ~~~~~~~~~~~~~~~~~~     
chase.cpp:166:9: note: in expansion of macro 'rep'
  166 |         rep(j, edges[i].size()){
      |         ^~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30