Submission #1082225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082225		anton	Harbingers (CEOI09_harbingers)	C++17	100 / 100	129 ms	31436 KiB

harbingers

#include<bits/stdc++.h>
    
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define point complex<ll>
const short OP_RESIZE = 0;
const short OP_SET = 1;
    
const ll MAX_SZ = 100001;
    
struct PStack{
    array<point, MAX_SZ> elems;
    int sz= 0;
    vector<short> ops;
    vector<int> resizes;
    vector<pair<int, point>> sets;
    void resize(ll new_sz){
        ops.push_back(OP_RESIZE);
        resizes.push_back(sz);
        sz = new_sz;
    }
    
    void set(int pos, point elem){
        ops.push_back(OP_SET);
        sets.push_back({pos, elems[pos]});
        elems[pos] = elem;
    }
    void push_back(point p){
        set(sz, p);
        resize(sz+1);
    }
    
    void undo(){
        short tp = ops.back();
        ops.pop_back();
        if(tp == OP_RESIZE){
            sz = resizes.back();
            resizes.pop_back();
        }
        else{
            elems[sets.back().first] = sets.back().second;
            sets.pop_back();
        }
    }
    void go_back(ll target_sz){
        while(ops.size()>target_sz){
            undo();
        }
    }
};
    
ll cross(point a, point b){
    return (a*conj(b)).imag();
}
ll dot(point a, point b){
    return (a*conj(b)).real();
}
bool ok(point a, point b, point c){
    return cross(b-a, c-b)>0;
}
    
struct Hull{
    PStack pts;
    
    void push_back(point e){
        if(pts.sz>1){
            ll cur = -1;
            for(ll step = (1<<20); step>=1; step/=2){
                if(cur+step+1<pts.sz){
                    if(ok(pts.elems[cur+step], pts.elems[cur+step+1], e)){
                        cur+=step;
                    }
                }
            }
            pts.resize(cur+2);
        }
        pts.push_back(e);
    }
    
    ll get_min(point normal){
        /*cout<<"getting at "<<normal.real()<<" "<<normal.imag()<<endl;
        for(ll i = 0; i<pts.sz; i++){
            cout<<pts.elems[i].real()<<" "<<pts.elems[i].imag()<<endl;
        }
        cout<<"done "<<endl;*/
        if(pts.elems.size() == 0){
            return 0;
        }
        ll cur = 0;
    
        for(ll step = (1<<20); step>=1; step/=2){
            if(cur+step<pts.sz){
                if(dot(normal, pts.elems[cur+step])<dot(normal, pts.elems[cur+step-1])){
                    cur+=step;
                }
            }
        }
        return dot(pts.elems[cur], normal);
    }
};
    
    
vector<pii> params;
vector<ll> dp_res;
array<vector<pii>, MAX_SZ> adj;
    
void dfs(int u,int anc, ll depth, Hull& h){
    int ops_sz = h.pts.ops.size(); 
    ll dp_cur = h.get_min({params[u].first, 1LL})-(ll)(params[u].first)*depth + (ll)(params[u].second);
    //cout<<u<<" "<<dp_cur<<endl;
    h.push_back({depth, dp_cur});
    dp_res[u] = dp_cur;
    
    for(auto e: adj[u]){
        if(e.first!=anc){
            dfs(e.first,u, depth-e.second, h);
        }
    }
    h.pts.go_back(ops_sz);
    
}

void dfs0(int u, int a){
    for(int i = 0; i<adj[u].size(); i++){
        auto e= adj[u][i];
        if(e.first!=a){
            dfs0(e.first, u);
        }
        else{
            swap(adj[u][i], adj[u].back());
            adj[u].pop_back();
            i--;
        }
    }
}
    
signed main(){
    int n;
    cin>>n;
    
    for(int i = 0; i<n-1; i++){
        ll u, v, d;
        cin>>u>>v>>d;
        u--;v--;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }

    dfs0(0, -1);
    for(int i = 0; i<n; i++){
        adj[i].shrink_to_fit();
    }


    params.resize(n);
    
    for(int i = 1; i<n; i++){
        cin>>params[i].second>>params[i].first;
    }
    
    Hull h;
    
    dp_res.resize(n);

    dfs(0, -1, 0, h);
    for(int i  =1; i<n; i++){
        cout<<dp_res[i]<<" ";
    }
    cout<<endl;
    
}

Compilation message (stderr)

harbingers.cpp: In member function 'void PStack::go_back(long long int)':
harbingers.cpp:48:25: warning: comparison of integer expressions of different signedness: 'std::vector<short int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   48 |         while(ops.size()>target_sz){
      |               ~~~~~~~~~~^~~~~~~~~~
harbingers.cpp: In function 'void dfs0(int, int)':
harbingers.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i = 0; i<adj[u].size(); i++){
      |                    ~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100