Submission #1120466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120466		HuyAT	Fireworks (APIO16_fireworks)	C++14	7 / 100	19 ms	21656 KiB

fireworks

#include<bits/stdc++.h>
#define newl '\n'

const int N = 3e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

long long w[N + 1],au[N + 1],bu[N + 1],n,m;
std::multiset<long long> slope[N + 1];
std::vector<int> adj[N + 1];

void readData(){
    std::cin >> n >> m;
    for(int i = 2;i <= n;++i){
        long long p;
        std::cin >> p >> w[i];
        adj[p].emplace_back(i);
    }
    for(int i = 1;i <= m;++i){
        long long p;
        std::cin >> p >> w[n + i];
        adj[p].emplace_back(n + i);
    }
}
long long eval(long long cnt,long long a,long long b,const std::multiset<long long> &s){
    ///evaluate the function at slope changing point position (int)s.size() - cnt + 1 /// 1 index
    long long last = *s.rbegin();
    long long ans = a * last + b;
    auto it = s.rbegin();
    int i = 1;
    while(i < cnt){
        ans -= (a - i) * (*it - *next(it));
        it = next(it);
        ++i;
    }
    return ans;
}
long long opt(long long a,long long b,const std::multiset<long long> &s){
    assert(a > 0);
    return eval(a,a,b,s);
}
void fix(long long &a,long long &b,std::multiset<long long> &s){
    long long opt_y = opt(a,b,s);
    while((int)s.size() > 2){
        s.erase(s.begin());
        s.erase(prev(s.end()));
    }
    a = 1;
    b = opt_y - *s.rbegin();
}
///opt_y = 1 * x - b
///-b = -x + opt_y
///b = -opy_y + x I GOT THIS PART WRONG
void get_size(int u = 1){
    for(int v : adj[u]){
        w[v] += w[u];
        get_size(v);
    }
}
void dfs(int u = 1){
    int heavy = 0;
    for(int v : adj[u]){
        dfs(v);
        if(slope[v].size() > slope[heavy].size()){
            heavy = v;
        }
    }
    if(heavy == 0){
        au[u] = 1;
        bu[u] -= w[u];
        slope[u].insert(w[u]);
        slope[u].insert(w[u]);
    }else{
        au[u] = au[heavy];
        bu[u] = bu[heavy];
        slope[u].swap(slope[heavy]);
        for(int v : adj[u]){
            if(v == heavy){
                continue;
            }
            for(long long val : slope[v]){
                slope[u].insert(val);
            }
            au[u] += au[v];
            bu[u] += bu[v];
        }
//        if(u == 1){
//            std::cout << au[u] << " " << bu[u] << " " << slope[u].size() << newl;
//        }
        fix(au[u],bu[u],slope[u]);
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    get_size();
    dfs();
    std::cout << opt(au[1],bu[1],slope[1]);

//    std::cout << w[2] << newl;
//    for(int i = 1;i <= m;++i){
//        std::cout << w[n + i] << " ";
//    }
//    std::cout << newl;
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45