Submission #955390

#	Time	Username	Problem	Language	Result	Execution time	Memory
955390		Unforgettablepl	Harbingers (CEOI09_harbingers)	C++17	30 / 100	137 ms	19904 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){}
    line(){}
    int operator()(int x) const{
        return m*x+n;
    }
};

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

line lines[100001];

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

void update(node* curr,int32_t x, vector<pair<node*,int32_t>> &updates){
    int mid = (curr->L+curr->R)/2;
    bool betterleft = lines[curr->lin](curr->L) > lines[x](curr->L);
    bool betterright = lines[curr->lin](curr->R) > lines[x](curr->R);
    bool bettermid = lines[curr->lin](mid) > lines[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);
vector<pair<node*,int32_t>> updates;


void dfs(int32_t x,int32_t p,int32_t depth){
    DP[x] = S[x]+V[x]*depth+ query(head,V[x]);
    int32_t old_len = updates.size();
    lines[x] = line(-depth,DP[x]);
    update(head,x,updates);
    for(auto&i:adj[x])if(i.first!=p){
        dfs(i.first,x,depth+i.second);
    }
    while(updates.size()>old_len){
        updates.back().first->lin = updates.back().second;
        updates.erase(--updates.end());
    }
}

int32_t main(){
//    freopen("harbingers.in","r",stdin);
//    freopen("harbingers.out","w",stdout);
    int32_t n;
    cin >> n;
    for(int32_t i=1;i<n;i++){
        int32_t u,v,d;cin>>u>>v>>d;
        adj[u].emplace_back(v,d);
        adj[v].emplace_back(u,d);
    }
    for(int32_t i=2;i<=n;i++)cin>>S[i]>>V[i];
    lines[0] = line(0,0);
    update(head,0,updates);
    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(int32_t, int32_t)':
harbingers.cpp:19:15: warning: 'node::R' will be initialized after [-Wreorder]
   19 |     int32_t L,R;
      |               ^
harbingers.cpp:18:11: warning:   'node* node::left' [-Wreorder]
   18 |     node *left,*right;
      |           ^~~~
harbingers.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     node(int32_t L,int32_t R): L(L), R(R), left(nullptr), right(nullptr), lin(0){}
      |     ^~~~
harbingers.cpp: In function 'void dfs(int32_t, int32_t, int32_t)':
harbingers.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<node*, int> >::size_type' {aka 'long unsigned int'} and 'int32_t' {aka 'int'} [-Wsign-compare]
   81 |     while(updates.size()>old_len){
      |           ~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 30 / 100