Submission #955401

#	Time	Username	Problem	Language	Result	Execution time	Memory
955401		Unforgettablepl	Harbingers (CEOI09_harbingers)	C++17	100 / 100	165 ms	32436 KiB

harbingers

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

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

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

line lines[100001];
node nodes[1500001];
int32_t c=1;

int query(node* curr,int x){
    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), curr->right==-1 ? INF : query(&nodes[curr->right], x));
    return min(lines[curr->lin](x), curr->left==-1 ? INF : query(&nodes[curr->left], x));
}

void update(int32_t curridx,int32_t x, vector<pair<int32_t ,int32_t>> &updates){
    node *curr = &nodes[curridx];
    int32_t 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(curridx,curr->lin);
        swap(x, curr->lin);
    }
    else if(betterleft and !bettermid){
        if(curr->left==-1) {
            nodes[++c] = node(curr->L, mid - 1);
            curr->left = c;
        }
        update(curr->left,x,updates);
    } else if(!bettermid){
        if(curr->right==-1) {
            nodes[++c] = node(mid+1, curr->R);
            curr->right = c;
        }
        update(curr->right,x,updates);
    } else if(betterleft){
        updates.emplace_back(curridx,curr->lin);
        swap(curr->lin,x);
        if(curr->right==-1) {
            nodes[++c] = node(mid+1, curr->R);
            curr->right = c;
        }
        update(curr->right,x,updates);
    } else {
        updates.emplace_back(curridx,curr->lin);
        swap(curr->lin, x);
        if(curr->left==-1) {
            nodes[++c] = node(curr->L, mid - 1);
            curr->left = c;
        }
        update(curr->left,x,updates);
    }
}



int DP[100001];
int32_t S[100001];
int32_t V[100001];
vector<pair<int32_t,int32_t>> adj[100001];
vector<pair<int32_t,int32_t>> updates;


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

int32_t main(){
//    freopen("harbingers.in","r",stdin);
//    freopen("harbingers.out","w",stdout);
    nodes[1] = node(1,1e9);
    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(1,0,updates);
    dfs(1,0,0);
    for(int32_t 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:20:15: warning: 'node::R' will be initialized after [-Wreorder]
   20 |     int32_t L,R;
      |               ^
harbingers.cpp:19:13: warning:   'int32_t node::left' [-Wreorder]
   19 |     int32_t left,right;
      |             ^~~~
harbingers.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     node(int32_t L,int32_t R): L(L), R(R), left(-1), right(-1), lin(0){}
      |     ^~~~
harbingers.cpp: In function 'void dfs(int32_t, int32_t, long long int)':
harbingers.cpp:96:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int32_t' {aka 'int'} [-Wsign-compare]
   96 |     while(updates.size()>old_len){
      |           ~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 100 / 100