oj.uz

Submission #377447

# Submission time Handle Problem Language Result Execution time Memory
377447 2021-03-14T08:29:00 Z lyc Harbingers (CEOI09_harbingers) C++14
100 / 100
 155 ms 26476 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int mxN = 1e5+5;
const int lgN = 17;

int N, S[mxN], V[mxN];
vector<ii> al[mxN];

int d[mxN];
ll dp[mxN];

struct Line {
    ll m, c;
    ll eval(int x) {
        return (ll)m*x + c;
    }
};

struct PConvexHull {
    Line ch[mxN];
    int pa[mxN][lgN], n;

    PConvexHull() { n = 0; }

    long double POI(Line p, Line q) { return (long double)(p.c-q.c)/(q.m-p.m); }
    bool redundant(Line p, Line q, Line l) { return POI(p,l) >= POI(q,l); }

    int add(int p, Line l) {
        if (p >= 0) {
            if (pa[p][0] != -1 && redundant(ch[pa[p][0]], ch[p], l)) {
                RFOR(k,lgN-1,0) if (pa[p][k] != -1 && pa[pa[p][k]][0] != -1) {
                    if (redundant(ch[pa[pa[p][k]][0]], ch[pa[p][k]], l)) {
                        p = pa[p][k];
                    }
                }
                p = pa[p][0];
            }
            if (l.m == ch[p].m) return p; // same grad doesn't make pa redundant => redundant
        }
        ch[n] = l;
        pa[n][0] = p;
        FOR(k,1,lgN-1) pa[n][k] = (pa[n][k-1] == -1 ? -1 : pa[pa[n][k-1]][k-1]);
        return n++;
    }

    ll query(int p, int x) {
        if (pa[p][0] != -1 && ch[pa[p][0]].eval(x) >= ch[p].eval(x)) {
            RFOR(k,lgN-1,0) if (pa[p][k] != -1 && pa[pa[p][k]][0] != -1) {
                if (ch[pa[pa[p][k]][0]].eval(x) >= ch[pa[p][k]].eval(x)) {
                    p = pa[p][k];
                }
            }
            p = pa[p][0];
        }
        return ch[p].eval(x);
    }
} ch;

void dfs(int u, int p, int chi) {
    if (u > 1) {
        //dp[u] = 1e18;
        //for (int v = p; v != 0; v = pa[v]) {
        //    dp[u] = min(dp[u], dp[v] + (ll)-d[v]*V[u]);
        //}
        //dp[u] += (ll)V[u]*d[u] + S[u];
        dp[u] = -ch.query(chi, V[u]) + (ll)V[u]*d[u] + S[u];
    }
    chi = ch.add(chi, {d[u], -dp[u]}); // negate -d[u], dp[u] for min
    //TRACE(u _ d[u] _ dp[u] _ chi _ ch.pa[chi][0]);

    for (ii& v : al[u]) if (v.first != p) {
        //pa[v.first] = u;
        d[v.first] = d[u]+v.second;
        dfs(v.first,u,chi);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int Ui, Vi, Di; cin >> Ui >> Vi >> Di;
        al[Ui].push_back(ii(Vi,Di));
        al[Vi].push_back(ii(Ui,Di));
    }
    FOR(i,2,N){
        cin >> S[i] >> V[i];
    }

    d[1] = 0;
    dfs(1,0,-1);

    FOR(i,2,N){
        cout << dp[i] << ' ';
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 5 ms 3308 KB Output is correct
3 Correct 66 ms 13164 KB Output is correct
4 Correct 98 ms 17792 KB Output is correct
5 Correct 108 ms 22000 KB Output is correct
6 Correct 155 ms 26476 KB Output is correct
7 Correct 77 ms 16396 KB Output is correct
8 Correct 143 ms 22376 KB Output is correct
9 Correct 151 ms 23916 KB Output is correct
10 Correct 129 ms 22908 KB Output is correct