Submission #1121630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121630		HuyAT	Fireworks (APIO16_fireworks)	C++14	100 / 100	356 ms	114508 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 f[N + 1],w[N + 1],bu[N + 1],shift[N + 1],n,m;
std::multiset<long long> slopel[N + 1],sloper[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);
    }
}
void add_dec(std::multiset<long long> &l,std::multiset<long long> &r,long long &b,long long x,long long left_shift){
    if(x <= *r.begin()){
        l.insert(x + left_shift);
    }else{
        long long x1 = *r.begin();
        r.insert(x);
        l.insert(x1 + left_shift);
        b += x - x1;
        r.erase(r.begin());
    }
}
void add_inc(std::multiset<long long> &l,std::multiset<long long> &r,long long &b,long long x,long long left_shift){
    if(x >= *l.rbegin() - left_shift){
        r.insert(x);
    }else{
        long long x1 = *l.rbegin() - left_shift;
        l.insert(x + left_shift);
        r.insert(x1);
        b += x1 - x;
        l.erase(prev(l.end()));
    }
}
void fix(int u){
    while((int)sloper[u].size() > 1){
        sloper[u].erase(prev(sloper[u].end()));
    }
    long long x = *prev(slopel[u].end());
    slopel[u].erase(prev(slopel[u].end()));
    slopel[u].insert(x + w[u]);
    shift[u] += w[u];
}
///opt_y = 1 * x + b
///b = opt_y - x
///b = -opy_y + x
void get_size(int u = 1){
    f[u] += w[u];
    for(int v : adj[u]){
        f[v] += f[u];
        get_size(v);
    }
}
void dfs(int u = 1){
    int heavy = 0;
//    if(u == )
    for(int v : adj[u]){
        dfs(v);
        if(slopel[v].size() + sloper[v].size() > slopel[heavy].size() + sloper[heavy].size()){
            heavy = v;
        }
    }
    if(heavy == 0){
        slopel[u].insert(f[u]);
        sloper[u].insert(f[u]);
    }else{
        bu[u] = bu[heavy];
        shift[u] = shift[heavy];
        slopel[u].swap(slopel[heavy]);
        sloper[u].swap(sloper[heavy]);
        for(int v : adj[u]){
            if(v == heavy){
                continue;
            }
            for(long long val : slopel[v]){
                long long x = val - shift[v];
                add_dec(slopel[u],sloper[u],bu[u],x,shift[u]);
            }
            for(long long val : sloper[v]){
                long long x = val;
                add_inc(slopel[u],sloper[u],bu[u],x,shift[u]);
            }
            bu[u] += bu[v];
        }
        fix(u);
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    get_size();
    dfs();
    std::cout << bu[1] << newl;
//    for(int i = 1;i <= n + m;++i){
//        std::cout << i << " " << bu[i] << newl;
//    }
//    std::cout << newl;
//    for(long long t : slope[1]){
//        std::cout << t << " ";
//    }
//    std::cout << w[2] << newl;
//    std::cout << newl;
//    for(int i = 1;i <= m;++i){
//        std::cout << w[n + i] << " ";
//    }
//    std::cout << newl;
    return 0;
}

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