Submission #959623

#	Time	Username	Problem	Language	Result	Execution time	Memory
959623		fucfan	Harbingers (CEOI09_harbingers)	C++14	0 / 100	155 ms	33360 KiB

harbingers

#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define ll long long
#define BIT(a , b) (((a) >> (b)) & 1)
#define flip(a , b) ((a) ^ (1 << (b)))
#define pii pair<int, int>
#define pb push_back
#define nl cout << "\n";
#define __ <<" "<<
#define mem(a, b) memset((a), (b), sizeof((a)))
#define all(c) (c).begin(), (c).end()
#define add(x , y) ((x) + (y) >= mod ? ((x) + (y) - mod) : ((x) + (y)))
#define file "test"
#define Times cerr << "\nTime run: " << clock() / 1000.0 << " ms\n";
using namespace std;

const ll oo = 2e18 + 7;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int LOG = 20;
const int base = 31;

void run_with_file(){
    if(fopen(file".inp" , "r")){
        freopen(file".inp", "r" , stdin);
        freopen(file".out", "w" , stdout);
    }
}

int n;
vector <pii> adj[N];
ll s[N] , v[N];
ll dp[N];

struct line_container{
    struct line{
        ll a , b;
        int id;

        ll cal(ll x){
            return a * x + b;
        }
    };

    vector <line> vt;

    ll intersect(line l1 , line l2){
        // assert(l1.a - l2.a == 0);
        return (l2.b - l1.b) / (l1.a - l2.a);
    }

    void add_line(line l3){
        if(vt.size() < 2) return vt.pb(l3) , void();
        line l2 = vt.back();
        vt.pop_back();
        line l1 = vt.back();
        while(vt.size() >= 2 && intersect(l3 , l1) < intersect(l2 , l1)){
            l2 = vt.back();
            vt.pop_back();
            l1 = vt.back();
        }
        if(intersect(l3 , l1) < intersect(l2 , l1)){
            vt.push_back(l3);
        }
        else{
            vt.push_back(l2);
            vt.push_back(l3);
        }
    }

    ll search(ll x){
        int l = 0;
        int r = (int) vt.size() - 1;

        while(l <= r){
            int mid = (l + r) >> 1;

            ll lef , rig;
            if(mid == (int)vt.size() - 1) rig = oo;
            else rig = intersect(vt[mid] , vt[mid + 1]);
            if(mid == 0) lef = -oo;
            else lef = intersect(vt[mid] , vt[mid - 1]);

            if(x > rig) l = mid + 1;
            if(x < lef) r = mid - 1;
            if(lef <= x && x <= rig) return vt[mid].cal(x);
        }

        return 0;
    }
} cht;

void dfs(int i , int p , ll dis){
    // cout << i << '\n';
    for(auto it : adj[i]){
        int j = it.fi;
        int w = it.se;
        if(j == p) continue;
        dp[j] = cht.search(v[j]) + (dis + w) * v[j] + s[j];
        cht.add_line({-dis - w , dp[j] , j});
        dfs(j , i , dis + w);
        // cout << cht.vt.size() << '\n';
        // cout << i << '\n';
        // for(auto j : cht.vt) cout << j.a << ' ' << j.b << ' ' << j.id << "/ ";
        // nl;
        if(cht.vt.size()) if(cht.vt.back().id == j) cht.vt.pop_back();
    }
}

void inp(){
    cin >> n;
    for(int i = 1 ; i < n ; i++){
        int u , v , w;
//        u = i;
//        v = u + 1;
//        w = 10000;
        cin >> u >> v >> w;
        adj[u].pb({v , w});
        adj[v].pb({u , w});
    }
    for(int i = 2 ; i <= n ; i++){
         cin >> s[i] >> v[i];
//        s[i] = 1000000000;
//        v[i] = 1000000000;
    }
}

void solve(){
    cht.vt.pb({0 , 0 , 1});
    dfs(1 , 0 , 0);

    for(int i = 2 ; i <= n ; i++) cout << dp[i] << ' ';
}

int main(){
    // cin.tie(0)->sync_with_stdio(false);
    run_with_file();
    int test_case = 1;
    //cin >> test_case;
    while(test_case--){
        inp();
        solve();
    }
}

/*      UwU      */

Compilation message (stderr)

harbingers.cpp: In function 'void run_with_file()':
harbingers.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(file".inp", "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(file".out", "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100