Submission #1136612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136612		TgX_2	Harbingers (CEOI09_harbingers)	C++20	100 / 100	72 ms	29252 KiB

harbingers

/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

#include <bits/stdc++.h>
using   namespace std;

#ifdef TGX 
#include "debug.h"
#else 
#define debug(...)
#endif 

#define FOR(i, a, b)       for (int i = (a), _b = (b); i <= _b; i += 1)
#define FORD(i, a, b)      for (int i = (a), _b = (b); i >= _b; i -= 1)

#define fi                 first
#define se                 second
#define pb                 push_back
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"
#define ___                << " "

#define ______________TgX______________ main()
#define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

struct custom {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<class T1, class T2> using cmap = unordered_map<T1, T2, custom>;

template<typename T1, typename T2> 
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2> 
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

class PersistentCHT {
private:
    struct Line {
        int a, b;

        double intersectX(const Line &other) const {
            return (other.b - b) * 1.0 / (a - other.a);
        }

        int eval(const int &x) {
            return a * x + b;
        }
    };

    int top = 0, n;
    vector<Line> hull;
    stack<pair<pair<int, int>, Line>> st;

    void build() {
        hull.resize(n + 7, {0, 0});
    }

    bool isRedundant(const Line &pre, const Line &cur, const Line &nex) {
        return (cur.intersectX(pre) <= nex.intersectX(cur));
    }

    void add_line(const int &a, const int &b) {
        int l = 1, r = top - 1, ans = top;
        Line cur = {a, b};
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (isRedundant(cur, hull[mid], hull[mid - 1])) {
                ans = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        st.push({{ans, top}, hull[ans]});
        top = ans + 1;
        hull[ans] = cur;
    }

    int get_query(const int &x) {
        int l = 0, r = top - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if (hull[mid].eval(x) >= hull[mid + 1].eval(x)) l = mid + 1;
            else r = mid;
        }
        return hull[l].eval(x);
    }

    void rollback() {
        assert(!st.empty());
        int pos = st.top().fi.fi;
        top = st.top().fi.se;
        Line cur = st.top().se;
        hull[pos] = cur;
        st.pop();
    }

public: 
    void build(int _n) {
        n = _n;
        build();
    }

    void add(const int &a, const int &b) {
        add_line(a, b);
    }

    int get(const int &x){
        return get_query(x);
    }

    void roll() {
        rollback();
    }
} pcht;

const int maxn = 1e5 + 7;
int n, w[maxn], s[maxn];
vector<pair<int, int>> g[maxn];

int h[maxn], dp[maxn];
void dfs(int u, int pre) {
    // debug(u, pre);
    dp[u] = s[u] * h[u] + w[u] + pcht.get(s[u]);
    pcht.add(-h[u], dp[u]);

    for(const pair<int, int> &val : g[u]) {
        int v = val.fi, w = val.se;
        if (v == pre) continue;
        h[v] = h[u] + w;
        dfs(v, u);
    }
    pcht.roll();
}


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

    FOR(i, 2, n) cin >> w[i] >> s[i];
    pcht.build(n);
    dfs(1, -1);
    FOR(i, 2, n) cout << dp[i] ___ ;
    // pcht.build(n);
}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }
    process();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." __ ;
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message (stderr)

harbingers.cpp:28:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | #define ______________TgX______________ main()
      |                                         ^~~~
harbingers.cpp:177:1: note: in expansion of macro '______________TgX______________'
  177 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen("temp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("temp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100