Submission #1123412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123412		TVSown	Harbingers (CEOI09_harbingers)	C++20	60 / 100	94 ms	15300 KiB

harbingers

///*** Sown_Vipro ***///
/// ->NHI QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
#define ll long long
//#define int long long
const string NAME = "harb";
const int N = 1e5 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
void maxi(int &x, int y){ if(x < y) x = y; }
void mini(long long &x, long long y){ if(x > y) x = y; };
void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); };
int n;
pi s[N];
vector<pi> e[N];

namespace sub1{
    int TIME;
    int in[N], out[N], t[N], p[N], d[N];
    long long dp[N];
    void pre(int u){
        in[u] = ++TIME;
        for(pi edge : e[u]){
            int v = edge.F, w = edge.S;
            if(v != p[u]){
                p[v] = u;
                d[v] = d[u] + w;
                pre(v);
            }
        }
    }

    bool cmp(int u, int v){
        return in[u] < in[v];
    }

    long long f(int u){
        int sum = 0, v = p[u];
        long long res = 1e18;
        while(v){
//            cout << v << " " << dp[v] << " " << (d[u] - d[v]) * s[u].S << " " << s[u].F << "\n";
            mini(res, dp[v] + 1ll * (d[u] - d[v]) * s[u].S + s[u].F);

            v = p[v];
        }
        return res;
    }

    void solve(){
        pre(1);

        FOR(u, 1, n) t[u] = u;
        sort(t + 1, t + 1 + n, cmp);
//        cout << f(2);
        FOR(i, 2, n){
            int u = t[i];
            dp[u] = f(u);
        }

        FOR(u, 2, n) cout << dp[u] << " ";
    }
}

namespace sub2{
//    #define int long long

    struct Line {
        mutable ll k, m, p;
        bool operator<(const Line& o) const { return k < o.k; }
        bool operator<(ll x) const { return p < x; }
    };

    struct LineContainer : multiset<Line, less<>> {
        // (for doubles, use inf = 1/.0, div(a,b) = a/b)
        static const ll inf = LLONG_MAX;
        ll div(ll a, ll b) { // floored division
            return a / b - ((a ^ b) < 0 && a % b); }
        bool isect(iterator x, iterator y) {
            if (y == end()) return x->p = inf, 0;
            if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
            else x->p = div(y->m - x->m, x->k - y->k);
            return x->p >= y->p;
        }
        void add(ll k, ll m) {
            auto z = insert({k, m, 0}), y = z++, x = y;
            while (isect(y, z)) z = erase(z);
            if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
            while ((y = x) != begin() && (--x)->p >= y->p)
                isect(x, erase(y));
        }
        ll query(ll x) {
            assert(!empty());
//            cout << size() << "\n";
            auto l = *lower_bound(x);
            return l.k * x + l.m;
        }
    } hull;

    int m, root;
    int t[N], ver[N], d[N];
    long long dp[N];

    void getLine(int u, int p){
        t[++m] = u;
        ver[u] = m;
        root = u;
        for(pi edge : e[u]){
            int v = edge.F, w = edge.S;

            if(v != p){
                getLine(v, u);
            }
        }
    }

    void caldist(int u, int p){
        for(pi edge : e[u]){
            int v = edge.F, w = edge.S;

            if(v != p){
                d[v] = d[u] + w;
                caldist(v, u);
            }
        }
    }

    void solve(){

        getLine(1, 0);
        m = d[root] = 0;
        getLine(root, 0);
        caldist(1, 0);
        hull.add(d[1], -dp[1]);

        FOR(i, ver[1] + 1, n){
            int u = t[i];
            dp[u] = 1ll * -hull.query(s[u].S) + 1ll * d[u] * s[u].S + s[u].F;
            hull.add(d[u], -dp[u]);
        }

        hull.clear();

        hull.add(d[1], -dp[1]);
        REP(i, ver[1] - 1, 1){
            int u = t[i];
            dp[u] = 1ll * -hull.query(s[u].S) + 1ll * d[u] * s[u].S + s[u].F;
            hull.add(d[u], -dp[u]);
        }

        FOR(u, 2, n) cout << dp[u] << " ";
    }
}

void solve(){
    cin >> n;
    FOR(i, 2, n){
        int u, v, w; cin >> u >> v >> w;
        e[u].pb({v, w});
        e[v].pb({u, w});
    }

    FOR(u, 2, n) cin >> s[u].F >> s[u].S;
//    sub2::solve();
    if(n <= 2500){
        sub1::solve();
    }else{
        sub2::solve();
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100