Submission #847138

#	Time	Username	Problem	Language	Result	Execution time	Memory
847138		Shreyan_Paliwal	Harbingers (CEOI09_harbingers)	C++17	80 / 100	140 ms	22608 KiB

harbingers

// // #pragma GCC optimize("Ofast")
// #include <bits/stdc++.h>
// using namespace std;

// template<int SZ> struct Tree {
//     vector<pair<int,int>> adj[SZ];
//     void init(int n) {
//         for (int i = 0; i < n-1; i++) {
//             int a, b, c; cin >> a >> b >> c; a--, b--;
//             adj[a].push_back({b,c});
//             adj[b].push_back({a,c});
//         }
//     }
// };

// #define f first
// #define s second

// const int maxn = 100005;

// int n;
// Tree<maxn> tree;
// pair<int,int> v[maxn];
// int dist[maxn];
// int ans[maxn];

// struct F {
//     int a, b;
//     F() {}
//     F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; }
//     bool operator<(F o) const { return a*o.b < b*o.a; }
//     bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
//     int m, b;
//     int operator()(int x) { return m*x + b; }
//     F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// struct ND {
//     L v;
//     ND *l, *r;

//     ND(int m, int b) { v = L{m, b}; l = r = nullptr; }
//     ND(ND* _l, ND* _r) { v = L{0, 0}; _l = _r = nullptr; }
// };
// struct Node {
//     L v;
//     Node *l, *r;
//     Node(L x) : v(x), l(nullptr), r(nullptr) {}
//     Node(Node* _l, Node* _r) : l(_l), r(_r) { v = L{0ll, 0ll}; }
// };
// template<int SZ> struct PersArray {
//     Node* roots[SZ];
//     int end[SZ];
//     Node* build(int l, int r) {
//         if (l == r) { return new Node(L{0ll, 0ll}); }
//         int m = (l + r) >> 1;
//         return new Node(build(l, m), build(m+1, r));
//     }
//     void init() { roots[0] = build(0, n-1); }
//     Node* UPD(Node* nd, int K, L V, int l, int r) {
//         if (l == r) { return new Node(V); }
//         int m = (l + r) >> 1;
//         if (K <= m) return new Node(UPD(nd->l, K, V, l, m), nd->r);
//         else return new Node(nd->l, UPD(nd->r, K, V, m+1, r));
//     }
//     L QRY(Node* nd, int K, int l, int r) {
//         if (l == r) return nd->v;
//         int m = (l + r) >> 1;
//         if (K <= m) return QRY(nd->l, K, l, m);
//         else return QRY(nd->r, K, m+1, r);
//         return L{0ll, 0ll};
//     }
//     inline L qry(int K, int T) {
//         return QRY(roots[T], K, 0, n-1);
//     }
//     inline void upd(int K, L V, int T, int Tp) {
//         roots[T] = UPD(roots[Tp], K, V, 0, n-1);
//     }
// };

// struct CHT {
//     PersArray<maxn> pers;
//     void add(int nd, int par, L l) {
//         int sz = pers.end[par];
//         while (sz >= 2 && (pers.qry(sz-2,par) ^ l) <= (pers.qry(sz-2,par) ^ pers.qry(sz-1, par)))
//             sz--;
//         pers.upd(sz, l, nd, par);
//         pers.end[nd] = sz + 1;
//     }
//     int qry(int nd, int x) {
//         int lo = 0, hi = pers.end[nd]-1;
//         while (lo < hi) {
//             int m = (lo + hi) >> 1;
//             if (pers.qry(m, nd)(x) > pers.qry(m+1, nd)(x))
//                 lo = m+1;
//             else 
//                 hi = m;
//         }
//         return (pers.qry(lo, nd))(x);
//     }
// };

// CHT cht;

// int cnt = 0;
// void dfs(int nd, int par, int parst) {
//     int cur = cnt++;

//     if (nd != 0)
//         ans[nd] =  v[nd].f + v[nd].s * dist[nd] + cht.qry(parst, v[nd].s);

//     cht.add(cur, parst, L{-dist[nd], ans[nd]});

//     for (auto i : tree.adj[nd])
//         if (i.f != par) {
//             dist[i.f] = dist[nd] + i.s;
//             dfs(i.f, nd, cur);
//         }

// }

// signed main() {
//     cin.tie(nullptr) -> ios::sync_with_stdio(false);
//     // freopen("main.in", "r", stdin);

//     cin >> n;
//     tree.init(n);
//     for (int i = 1; i < n; i++) cin >> v[i].f >> v[i].s;

//     cht.pers.init();

//     dfs(0, 0, 0);

//     for (int i = 1; i < n; i++)
//         cout << ans[i] << ' ';
//     cout << endl;

//     return 0;
// }

/************ PERSISTANT ARRAY ALGO ABOVE, EXCEEDS TIME DUE TO CONSTANTS AND ALSO MEMORY **************/
/************ CHT ALGO BELOW, PASSES **************/

// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define f first 
#define s second

struct F {
    int a, b;
    F() {}
    F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; }
    bool operator<(F o) const { return a*o.b < b*o.a; }
    bool operator<=(F o) const { return a*o.b <= b*o.a; }
};
struct L {
    int m, b;
    int operator()(int x) { return m*x + b; }
    F operator^(L o) { return F{b-o.b,o.m-m}; }
};

const int maxn = 100000;
int n;
vector<pair<int,int>> adj[maxn];
pair<int,int> v[maxn];

pair<int,L> removed[maxn];

int ans[maxn];

L CHT[maxn]; int cht_sz = 0;
void add(L l, int nd) {
    removed[nd] = {cht_sz, l};
    int lo = 0, hi = cht_sz - 1; // represents range for rightmost OLD ONE
    while (lo < hi) {
        int mid = (lo + hi) >> 1; // will test MID & (MID+1)
        if ((CHT[mid]^l) <= (CHT[mid]^CHT[mid+1]))
            hi = mid;
        else 
            lo = mid+1;
    }
    cht_sz = lo+1;
    // while (cht_sz >= 2 && (CHT[cht_sz-2]^l) <= (CHT[cht_sz-2]^CHT[cht_sz-1]))
    //     cht_sz--;
    swap(removed[nd].s, CHT[cht_sz++]);
}
int qry(int x) {
    int lo = 0, hi = cht_sz-1;
    while (lo < hi) {
        int m = (lo + hi) >> 1;
        if (CHT[m](x) > CHT[m+1](x)) 
            lo = m+1;
        else 
            hi = m;
    }
    return CHT[lo](x);
}
void restore(int nd) {
    cht_sz--;
    swap(removed[nd].s, CHT[cht_sz]);
    cht_sz = removed[nd].f;
}

void dfs(int nd, int par, int d) {
    add(L{-d, ans[nd]}, par);
    for (auto i : adj[nd])
        if (i.f != par) {
            ans[i.f] = v[i.f].f + v[i.f].s * (d + i.s) + qry(v[i.f].s);
            dfs(i.f, nd, d + i.s);
        }
    restore(par);
}

signed main() {
    // freopen("main.in", "r", stdin);

    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for (int i = 1; i < n; i++) cin >> v[i].f >> v[i].s;

    dfs(0, 0, 0);

    for (int i = 1; i < n; i++) cout << ans[i] << ' '; 
    cout << endl;
}

• Subtask 1: 80 / 100