Submission #933930

#	Time	Username	Problem	Language	Result	Execution time	Memory
933930		mraron	Harbingers (CEOI09_harbingers)	C++14	0 / 100	7 ms	7260 KiB

harbingers

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert
#define chkmn(x,y) (x)=min((x), (y))
#define chkmx(x,y) (x)=max((x), (y))

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
//using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
    T val=0;
    char c;
    
    bool neg=false;
    while((c=gc()) && !(c>='0' && c<='9')) {
        neg|=c=='-';
    }

    do {
        val=(val*10)+c-'0';
    } while((c=gc()) && (c>='0' && c<='9'));

    return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


struct line {
    ll m,b;
    ll at(ll x) const {
        return m*x+b;
    }
};

struct magic_stack {
    vector<line> lst;
    vector<line> popped;
    
    bool inter(line x, line y, line z) {
        return (x.b-y.b)*(-y.m+z.m)>=(y.b-z.b)*(-x.m+y.m);
    }
    
    int add(line l) {
        lst.push_back(l);
        int cnt=0;
        while(sz(lst)>2 && inter(lst[sz(lst)-3], lst[sz(lst)-2], lst.back())) {
            swap(lst[sz(lst)-2], lst.back());
            popped.push_back(lst.back());
            lst.pop_back();
            cnt++;
        }
        return cnt;
    }
    
    ll get(ll x) {
        int L=0, R=sz(lst)-1;
        while(L<R) {
            int mid=(L+R)/2;
            if(lst[mid].at(x)<lst[mid+1].at(x)) {
                R=mid;
            }else {
                L=mid+1;
            }
        }
        return lst[L].at(x);
    }
    
    void undo() {
        lst.push_back(popped.back());
        popped.pop_back();
        swap(lst.back(), lst[sz(lst)-2]);
    }
    
    void debug() {
        for(auto i:lst) cerr<<i.m<<" "<<i.b<<"\n";
    }
};

vector<pair<int,ll>> adj[100001];
ll s[100001], v[100001], ans[100001];
int todo[100010], st[100010];

void dfs(int x, magic_stack& ms, ll depth=0) {
    st[x]=1;
    if(x>1) {
        ans[x]=depth*v[x]+s[x];
        //~ LOG(ans[x]);
        if(ms.lst.size()>0) {
            ans[x]=min(ans[x], ms.get(v[x])+s[x]+depth*v[x]);
        }
        todo[x]=ms.add(line{-depth, ans[x]});
    }
    //~ LOG("here");
    for(auto i:adj[x]) {
        if(!st[i.xx]) {
            dfs(i.xx, ms, depth+i.yy);
        }
    }
    
    if(x>1) {
        //~ LOG(x);
        while(todo[x]) {
            todo[x]--;
            ms.undo();
        }
        ms.lst.pop_back();
    }
}

int main() {
    IO;
    freopen("harbringers.in", "r", stdin);
    freopen("harbringers.out", "w", stdin);
    int n;
    cin>>n;
    for(int i=0;i<n-1;++i) {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    for(int i=2;i<=n;++i) {
        cin>>s[i]>>v[i];
    }
    
    magic_stack ms;
    dfs(1, ms);
    for(int i=2;i<=n;++i) cout<<ans[i]<<" \n"[i==n];
    
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:159:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     freopen("harbringers.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:160:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |     freopen("harbringers.out", "w", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100