Submission #346764

#	Time	Username	Problem	Language	Result	Execution time	Memory
346764		gmyu	Harbingers (CEOI09_harbingers)	C++14	100 / 100	177 ms	17516 KiB

harbingers

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI09_harbingers
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007


bool debug;

int N;
vii adjlist[MAXV];
ll delay[MAXV], speed[MAXV], d[MAXV];
ll dp[MAXV];

void dfs0(int v, int pv, ll depth) {
    d[v] = depth;
    for(auto x : adjlist[v]) {
        if(x.fst == pv) continue;
        dfs0(x.fst, v, depth + (ll)x.snd);
    }
}

int q[MAXV];
double crossPoint(int v1, int v2) {
    return ((double)dp[v2] - (double)dp[v1]) / ((double)d[v2] - (double)d[v1]);
}
int bs_DP(int v, int hct) {
    if(hct==1) return q[0];
    if(hct==2) return (crossPoint(q[0], q[1]) > (double) speed[v]) ? q[0] : q[1];

    int lo = 0, hi = hct-1, mid = 0;
    while(lo < hi) {
        mid = (lo+hi)/2;
        if(mid == hct-1 || mid == 0) {
            lo = hi+1;
        } else if(crossPoint(q[mid-1], q[mid]) > (double) speed[v]) {
            hi = mid -1;
        } else if(crossPoint(q[mid], q[mid+1]) < (double) speed[v]) {
            lo = mid + 1;
        } else {
            lo = hi+1;
        }
    }
    /// double confirm
    while(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > (double) speed[v]) mid--;
    while(mid+1<=hct-1 && crossPoint(q[mid], q[mid+1]) < (double) speed[v]) mid++;

    return q[mid];
}
int bs_Hull(int v, int hct){
    if(hct==0) return 0;
    if(hct==1) return 1;
    if(hct==2) return (crossPoint(q[hct-2], q[hct-1]) < crossPoint(q[hct-1], v)) ? 2 : 1;

    if(crossPoint(q[hct-2], q[hct-1]) < crossPoint(q[hct-1], v)) return hct;

    int lo = 0, hi = hct-1, mid = 0;
    while(lo < hi) {
        mid = (lo+hi)/2;
        if(mid==0 || mid == hct-1) {
          lo = hi+1;
        } if(crossPoint(q[mid-1], q[mid]) > crossPoint(q[mid], v)) {
            hi = mid-1;
        } else if(crossPoint(q[mid], q[mid+1]) <=  crossPoint(q[mid], v)) {
            lo = mid+1;
        } else {
            lo = hi+1;
        }
    }
    /// double confirm
    if(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > crossPoint(q[mid], v)) mid--;
    if(mid+1<=hct-1 && crossPoint(q[mid], q[mid+1]) <= crossPoint(q[mid], v)) mid++;
    if(mid==0) return 1;

    return mid;
}
int bs_Hull2(int v, int hct){
    int l = 1, r = hct;
	while(l < r) {
		int mid = (l + r) / 2;
		if(crossPoint(v, q[mid-1]) < crossPoint(q[mid], q[mid-1])) r = mid;
		else l = mid + 1;
	}
	return l;
}

void dfs(int v, int pv, int hct) {
    if(debug) {
        cout << "work on " << v << endl;
        for(int i=0; i< hct; i++) cout << q[i] << " ";
        cout << endl;
    }

    dp[v] = delay[v] + speed[v] * d[v];
    if(hct>0) {
        int j = bs_DP(v, hct);
        ll ndp = dp[v] + dp[j] - d[j] * speed[v];
        dp[v] = min(dp[v], ndp);
    }
    if(debug) cout << v << " " << dp[v] << endl;

    int store = v;
    int hullReplace = bs_Hull2(v, hct);
    swap(store, q[hullReplace]);

    for(auto x : adjlist[v]) {
        if(x.fst == pv) continue;
        dfs(x.fst, v, hullReplace+1);
    }

    swap(store, q[hullReplace]);

}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    int i, j, k;

    cin >> N ;
    for(i=1;i<=N-1;i++) {
        int a, b, c; cin >> a >> b >> c;
        adjlist[a].pb(mp(b,c)); adjlist[b].pb(mp(a,c));
    }
    for(i=2;i<=N;i++) cin >> delay[i] >> speed[i];
    dfs0(1,0,0LL);
    if(debug) cout << "complete setup" << endl;

    for(auto x : adjlist[1]) {
        dfs(x.fst, 1, 0);
    }
    if(debug) cout << "complete calculation" << endl;

    for(i =2; i<=N; i++) cout << dp[i] << " ";
    cout << endl;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:151:12: warning: unused variable 'j' [-Wunused-variable]
  151 |     int i, j, k;
      |            ^
harbingers.cpp:151:15: warning: unused variable 'k' [-Wunused-variable]
  151 |     int i, j, k;
      |               ^

• Subtask 1: 100 / 100