Submission #1082190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082190		anton	Harbingers (CEOI09_harbingers)	C++17	40 / 100	137 ms	34496 KiB

harbingers

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define point complex<long long>
#define ll long long
const int OP_RESIZE = 0;
const int OP_SET = 1;

struct Op{
    int op_t;
    int a;
    point b;
};

const int MAX_SZ = 100001;

struct PStack{
    array<point, MAX_SZ> elems;
    int sz= 0;
    vector<Op> ops;
    void resize(int new_sz){
        ops.push_back(Op{OP_RESIZE, sz, 0});
        sz = new_sz;
    }
    
    void set(int pos, point elem){
        ops.push_back(Op{OP_SET, pos, elems[pos]});
        elems[pos] = elem;
    }
    void push_back(point p){
        resize(sz+1);
        set(sz, p);
        sz++;
    }

    void undo(Op op){
        if(op.op_t == OP_RESIZE){
            sz = op.a;
        }
        else{
            elems[op.a] = op.b;
        }
    }
    void go_back(int target_sz){
        while(ops.size()>target_sz){
            undo(ops.back());
            ops.pop_back();
        }
    }
};

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){
            int cur = 0;
            for(int 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+1);
        }
        pts.push_back(e);
    }

    ll get_min(point normal){
        //cout<<"getting at "<<normal.real()<<" "<<normal.imag()<<endl;
        /*for(int 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;
        }
        int cur = 0;

        for(int step = (1<<20LL); 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<vector<pii>> ch;
vector<pii> params;
vector<int> dp_res;
vector<vector<pii>> adj;

void dfs(int u,int anc, int depth, Hull& h){
    int ops_sz = h.pts.ops.size(); 
    int dp_cur = h.get_min({params[u].first, 1LL})-params[u].first*(depth) + 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);

}

signed main(){
    int n;
    cin>>n;

    adj.resize(n);
    for(int i = 0; i<n-1; i++){
        int u, v, d;
        cin>>u>>v>>d;
        u--;v--;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    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(int)':
harbingers.cpp:46:25: warning: comparison of integer expressions of different signedness: 'std::vector<Op>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         while(ops.size()>target_sz){
      |               ~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 40 / 100