Submission #747142

#	Time	Username	Problem	Language	Result	Execution time	Memory
747142		vjudge1	Harbingers (CEOI09_harbingers)	C++14	100 / 100	118 ms	30716 KiB

harbingers

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

#define             ll        long long
#define             ed        << "\n";
#define             el        cout<<'\n';
#define            ALL(s)     s.begin(),s.end()
#define             fi        first
#define             se        second
#define            task       "a"
#define            SQ(a)      (a)*(a)
#define            A(a)        abs(a)
#define            SZ(a)      ((int)(a.size()))
#define          REP(i,a,b)    for (int i = (a), _b = (b); i < _b; i++)
#define          FOR(i,a,b)    for (int i = (a), _b = (b); i <= _b; i++)
#define          FOD(i,r,l)    for(int i=r; i>=l; i--)
#define           MASK(x)      (1LL << (x))
#define           pii          pair<int,int>
#define            BIT(x, i)          ((x) >> (i) & 1)
#define int ll
const int mod = 1e9 + 7;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r) {
    return l + rd() % (r - l + 1);
}

int mul(ll a, ll b) {
    if(a >= mod) a %= mod;
    if(b >= mod) b %= mod;
    return 1LL * a * b % mod;
}

void ADD(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

int add(int a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    return a;
}

int pw(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1)
            res = mul(res, a);
        b = b >> 1;
        a = mul(a, a);
    }
    return res;
}

template <class T> inline bool minimize(T &a, const T &b) {
    return (a > b ? (a = b),1 : 0);
}

template <class T> inline bool maximize(T &a, const T &b) {
    return (a < b ? (a = b),1 : 0);
}

void ReadInp() {
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

#define task "ACQUIRE"
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}

//struct CHT{
//    struct LINE{
//        int slope, yInter;
//        LINE(int slope, int yInter) : slope(slope) , yInter(yInter){}
//
//        int val(int x) const{
//            return slope * x + yInter;
//        }
//
//        double intersect(const LINE &l) const{
//            double ds = slope - l.slope;
//            double dy = l.yInter - yInter;
//            return dy / ds;
//        }
//    };
//    vector <double> x;
//    vector <LINE> l ;
//
//    void init(int slope, int yInter){
//        x.push_back(- 1e12);
//        l.push_back(LINE(slope, yInter));
//    }
//
//    void addLine(int slope, int yInter){
//        LINE p (slope, yInter);
//        while(SZ(l) > 1 && p.intersect(l[l.size() - 2]) <= x.back()){
//            x.pop_back();
//            l.pop_back();
//        }
//
//        if(l.size()) x.push_back(p.intersect(l.back()));
//        l.push_back(p);
//    }
//
//    long long query(long long qx) const{
//        int id = upper_bound(x.begin(), x.end(), qx) - x.begin();
//        id --;
//        return l[id].val(qx);
//    }
//};



struct CHT {
    struct LINE {
        int slope, yInter;
        LINE(int slope = 0, int yInter = 0) : slope(slope), yInter(yInter) {}

        int val(int x) const{
            return slope * x + yInter;
        }

        double intersect(const LINE &l) const{
            double ds = slope - l.slope;
            double dy = l.yInter - yInter;
            return dy / ds;
        }
    } lines[100005];

    struct PAST {
        int pos, top;
        LINE past;

        PAST(int _pos, int _top, LINE _p) : pos(_pos), top(_top), past(_p) {}
    };

    vector <PAST> undo;
    int top;


    bool bad(LINE a, LINE b, LINE c) const {
        return b.intersect(a) >= c.intersect(a);
    }

    void addLine(int slope, int yInter) {
        int l = 2, r = top;
        int k = top + 1;
        LINE p (slope, yInter);

        while(l <= r) {
            int m = (l + r) / 2;
            if(bad(lines[m - 1], lines[m], p)) {
                k = m;
                r = m - 1;
            } else l = m + 1;
        }


        undo.push_back({k, top, lines[k]});
        lines[k] = p;
        top = k;
    }

    void roll_back() {
        if(undo.empty()) return;

        PAST p = undo.back();
        undo.pop_back();

        lines[p.pos] = p.past; top = p.top;
    }

    long long query(long long qx) {
        int l = 1, r = top;
        ll ans = 1e18;
        while(l <= r) {
            int m = (l + r) / 2;
            ll x = lines[m].val(qx);
            ll y = 1e18;
            if(m < top) y = lines[m + 1].val(qx);

            if(x > y) l = m + 1;
            else r = m - 1;

            ans = min(ans, min(x, y));
        }

        return ans ;
    }


} dp;


int n, m, k;
int a[100005];
int s[100005];
int d[100005];
int V[100005];
int f[100005];

vector <pair<int,int>> g[100005];

void dfs(int u, int p) {

    for(auto [v, c] : g[u]) if(v != p){
            d[v] = d[u] + c;

            f[v] = dp.query(V[v]) + d[v] * V[v] + s[v];

            dp.addLine(- d[v], f[v]);

            dfs(v, u);

            dp.roll_back();
        }
}

void sol() {
    cin >> n;

    FOR(i, 1, n - 1) {
        int u, v, d;
        cin >> u >> v >> d;
        g[u].push_back({v, d});
        g[v].push_back({u, d});
    }

    FOR(i, 2, n) cin >> s[i] >> V[i];

    dp.addLine(0, 0);
    dfs(1, 1);

    FOR(i, 2, n) cout << f[i] << ' ';
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ReadInp();
    int t = 1;  //cin >> t;
    while(t --) sol();
    return 0;
}

Compilation message (stderr)

harbingers.cpp:70: warning: "task" redefined
   70 | #define task "ACQUIRE"
      | 
harbingers.cpp:10: note: this is the location of the previous definition
   10 | #define            task       "a"
      | 
harbingers.cpp: In function 'void dfs(long long int, long long int)':
harbingers.cpp:212:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  212 |     for(auto [v, c] : g[u]) if(v != p){
      |              ^
harbingers.cpp: In function 'void ReadInp()':
harbingers.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100