Submission #346481

#	Time	Username	Problem	Language	Result	Execution time	Memory
346481		gmyu	Harbingers (CEOI09_harbingers)	C++14	0 / 100	160 ms	23916 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

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

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], qct;
double crossPoint(int v1, int v2) {
    return ((double)dp[v2] - (double)dp[v1]) / ((double)d[v2] - (double)d[v1]);
}
int bs(int v) {
    int lo = 0, hi = qct-1, mid = 0;
    while(lo < hi) {
        mid = (lo+hi)/2;
        if(debug) cout << "bs " << q[mid] << endl;
        if(mid == qct-1 || mid == 0) {
            lo = hi+1;
        } else if(crossPoint(q[mid-1], q[mid]) > speed[v]) {
            if(debug) cout << " .. hi goes down " << lo << " " << hi << endl;
            hi = mid -1;
        } else if(crossPoint(q[mid], q[mid+1]) < speed[v]) {
            if(debug) cout << " .. lo goes up " << lo << " " << hi << endl;
            lo = mid + 1;
        } else {
            if(debug) cout << " .. found " << q[mid] << endl;
            lo = hi+1;
        }
    }
    /// double confirm
    while(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > speed[v]) mid--;
    while(mid+1<=qct-1 && crossPoint(q[mid], q[mid+1]) < speed[v]) mid++;

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

    dp[v] = delay[v] + speed[v] * d[v];
    if(qct>0) {
        int j;
        if(qct==1) {
            j = q[0];
        } else if(qct==2) {
            j = q[0];
            if(crossPoint(q[0], q[1]) < speed[v]) j = q[1];
        } else {
            if(debug) cout << " .. go bs" << endl;
            j = bs(v);
            if(debug) cout << " .. bs find " << j;
        }
        ll ndp = dp[v] + dp[j] - d[j] * speed[v];
        dp[v] = min(dp[v], ndp);
    }
    if(debug) cout << v << " " << dp[v] << endl;

    vi store;
    store.clear();
    while(qct>=2 && crossPoint(qct-2, qct-1) > crossPoint(qct-1, v)) {
        store.pb(q[qct-1]);
        qct--;
    }
    q[qct] = v; qct++;

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

    qct--;
    for(int i = sz(store)-1; i>=0; i--) {
        q[qct] = store[i]; qct++;
    }
    store.clear();

}

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;

    qct = 0;
    dfs(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:145:12: warning: unused variable 'j' [-Wunused-variable]
  145 |     int i, j, k;
      |            ^
harbingers.cpp:145:15: warning: unused variable 'k' [-Wunused-variable]
  145 |     int i, j, k;
      |               ^

• Subtask 1: 0 / 100