Submission #955377

#	Time	Username	Problem	Language	Result	Execution time	Memory
955377		Unforgettablepl	Harbingers (CEOI09_harbingers)	C++17	60 / 100	185 ms	60240 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

struct line{
    int32_t m;int n;
    line(int m,int n):m(m),n(n){}
    int operator()(int x) const{
        return m*x+n;
    }
};

struct node{
    node *left,*right;
    int32_t L,R;
    line lin;
    node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0, INF){}
};

int query(node* curr,int x){
    if(curr==nullptr)return INF;
    int mid = (curr->L+curr->R)/2;
    if(mid==x)return curr->lin(x);
    if(mid<x)return min(curr->lin(x), query(curr->right, x));
    return min(curr->lin(x), query(curr->left, x));
}

void update(node* curr,line x, vector<pair<node*,line>> &updates){
    int mid = (curr->L+curr->R)/2;
    bool betterleft = curr->lin(curr->L) > x(curr->L);
    bool betterright = curr->lin(curr->R) > x(curr->R);
    bool bettermid = curr->lin(mid) > x(mid);
    if(!(betterleft or bettermid or betterright))return;
    if(bettermid and betterright and betterleft) {
        updates.emplace_back(curr,curr->lin);
        swap(x, curr->lin);
    }
    else if(betterleft and !bettermid){
        if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
        update(curr->left,x,updates);
    } else if(!bettermid){
        if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
        update(curr->right,x,updates);
    } else if(betterleft){
        updates.emplace_back(curr,curr->lin);
        swap(curr->lin,x);
        if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
        update(curr->right,x,updates);
    } else {
        updates.emplace_back(curr,curr->lin);
        swap(curr->lin, x);
        if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
        update(curr->left,x,updates);
    }
}



int DP[100001];
int32_t S[100001];
int32_t V[100001];
vector<pair<int32_t,int32_t>> adj[100001];
node* head = new node(1,1e9);

void dfs(int x,int p,int depth){
    DP[x] = S[x]+V[x]*depth+ query(head,V[x]);
    vector<pair<node*,line>> updates;
    update(head,line(-depth,DP[x]),updates);
    for(auto&i:adj[x])if(i.first!=p){
        dfs(i.first,x,depth+i.second);
    }
    for(auto&i:updates)i.first->lin=i.second;
}

int32_t main(){
//    freopen("harbingers.in","r",stdin);
//    freopen("harbingers.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
        int u,v,d;cin>>u>>v>>d;
        adj[u].emplace_back(v,d);
        adj[v].emplace_back(u,d);
    }
    for(int i=2;i<=n;i++)cin>>S[i]>>V[i];
    vector<pair<node*,line>> h;
    update(head,line(0,0),h);
    dfs(1,0,0);
    for(int i=2;i<n;i++)cout<<DP[i]<<' ';
    cout << DP[n] << '\n';
}

Compilation message (stderr)

harbingers.cpp: In constructor 'node::node(long long int, long long int)':
harbingers.cpp:18:15: warning: 'node::R' will be initialized after [-Wreorder]
   18 |     int32_t L,R;
      |               ^
harbingers.cpp:17:11: warning:   'node* node::left' [-Wreorder]
   17 |     node *left,*right;
      |           ^~~~
harbingers.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0, INF){}
      |     ^~~~

• Subtask 1: 60 / 100