Submission #1171448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171448		InvMOD	Harbingers (CEOI09_harbingers)	C++17	100 / 100	56 ms	25160 KiB

harbingers

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

using ll = long long;
using ld = long double;

struct Line{
    int a; ll b;
    Line(int a = 0, ll b = LLONG_MAX): a(a), b(b) {}
    ll f(ll x){return 1ll * a * x + b;}
    ld intersect(Line x){return (1.0l * b - x.b) / (1.0l * x.a - a);}
};

struct ConvexHullRollBack{

    stack<pair<int,Line>> history;

    vector<Line> hull; int cur_size;

    void init(int n){
        cur_size = 0;
        hull.resize(n + 1);
    }

    void ins(Line x){
        int l = -1, r = cur_size;
        while(l + 1 < r){
            int m = l + r >> 1;

            ld pre_intersect;
            if(m > 0){
                pre_intersect = hull[m].intersect(hull[m - 1]);
            }
            else pre_intersect = -1e15;

            if(x.intersect(hull[m]) <= pre_intersect){
                r = m;
            }
            else l = m;
        }

//        cout << "INS: " << x.a <<" " << x.b << "\n";
//        cout << "SIZE: " << cur_size <<" " << r + 1 << "\n\n";

        history.push({cur_size, hull[r]});
        hull[r] = x, cur_size = r + 1;
    }

    ll query(ll x){
        int l = -1, r = cur_size - 1;

//        cout << "Query: " << x << "\n";
//        for(int i = 0; i < cur_size; i++){
//            cout << hull[i].f(x) << " ";
//        } cout << "\n";

        while(l + 1 < r){
            int m = l+r>>1;

            if(hull[m].f(x) >= hull[m + 1].f(x)){
                l = m;
            }
            else r = m;
        }

        ll answer = hull[l + 1].f(x);
        answer = min(answer, hull[cur_size - 1].f(x));

//        cout << l <<" " << answer << "\n";
        return answer;
    }

    int snapshot(){
        return sz(history);
    }

    void rollback(int snipe){
        while(sz(history) > snipe){
            pair<int,Line> i = history.top(); history.pop();

            hull[cur_size - 1] = i.second;
            cur_size = i.first;
        }
    }
};

const int N = 1e5 + 5;

int speed[N];

ll dp[N], cur_dist[N];

pair<int,int> E[N];

basic_string<int> adj[N];

ConvexHullRollBack hull;

void dfs(int x){
    if(x) dp[x] += hull.query(speed[x]) + (1ll * cur_dist[x] * speed[x]);
    int snipe = hull.snapshot();

    hull.ins(Line(-cur_dist[x], dp[x]));

    for(int id : adj[x]){
        int v = E[id].first ^ x, w = E[id].second;
        if(v && !cur_dist[v]){
            cur_dist[v] = cur_dist[x] + 1ll * w;
            dfs(v);
        }
    }

    hull.rollback(snipe);
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i < n; i++){
        int u,v,w; cin >> u >> v >> w;
        u--, v--;
        E[i] = make_pair(u^v, w);
        adj[u].push_back(i);
        adj[v].push_back(i);
    }

    for(int i = 1; i <= n - 1; i++){
        cin >> dp[i] >> speed[i];
    }

    hull.init(n), dfs(0);

    for(int i = 1; i < n; i++) cout << dp[i] << " \n"[i == n - 1];
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100