Submission #724994

#	Time	Username	Problem	Language	Result	Execution time	Memory
724994		Trent	Harbingers (CEOI09_harbingers)	C++17	100 / 100	720 ms	24896 KiB

harbingers

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}

int aOff=0;

class line{
    private:
    int ar;
    public:
    ll b;
    line(int a, ll b){
        this->ar = a - aOff;
        this->b = b;
    }
    line(){}
    inline ll a(){return ar+aOff;}
    inline ll ev(ll x){return a() * x + b;}
};

ld intX(line a, line b){
    return (ld) (a.b-b.b) / (b.a() - a.a());
}

const int MN = 1e5 + 10, ME=17;
struct edge{int t, e;};
vector<edge> adj[MN];
int nex[MN][ME], ci=0; // one before next, array in increasing slope
line lin[MN];
ll ans[MN], s[MN], v[MN];

ll bes(ll x, int cur){
    ll ret = lin[cur].ev(x);
    for(int e = ME - 1; e >= 0; --e){
        int las = nex[cur][e];
        ret = min(ret, lin[las].ev(x));
        if(nex[las][0] != -1 && lin[las].ev(x) > lin[nex[las][0]].ev(x)) cur = nex[las][0];
    }
    ret = min(ret, lin[cur].ev(x));
    return ret;
}

void add(line toAdd, int firs){
    lin[ci] = toAdd;
    for(int e = ME - 1; e >= 0; --e){
        int las = nex[firs][e];
        if(nex[las][e] != -1 && intX(toAdd, lin[las]) < intX(toAdd, lin[nex[las][0]])) firs = las;
    }
    while(firs != -1 && nex[firs][0] != -1 && intX(toAdd, lin[firs]) < intX(lin[firs], lin[nex[firs][0]])) {
        firs=nex[firs][0];
    }
    nex[ci][0] = firs;
    REP(e, 1, ME) nex[ci][e] = nex[ci][e-1] == -1 ? -1 : nex[nex[ci][e-1]][e-1];
    ci++;
}

void dfs(int c, int p, int st){
    if(c != 1) ans[c] = bes(v[c], st) + s[c];
    for(auto [t, e] : adj[c]) if(t != p){
        aOff += e;
        line eLine(e, ans[c]);
        add(eLine, st);
        dfs(t, c, ci - 1);
        aOff -= e;
    }
}

signed main(){
    boost();
    int n; cin >> n;
    forR(e, n - 1){
        int a, b, d; cin >> a >> b >> d;
        adj[a].push_back({b, d});
        adj[b].push_back({a, d});
    }
    REP(i, 2, n + 1) cin >> s[i] >> v[i];
    dfs(1, -1, -1);

    REP(i, 2, n + 1) cout << ans[i] << " \n"[i == n];
}

Compilation message (stderr)

harbingers.cpp: In function 'bool operator<(pii, pii)':
harbingers.cpp:16:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   16 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                    ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100