Submission #1086477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086477		Thunnus	Harbingers (CEOI09_harbingers)	C++17	0 / 100	3 ms	2660 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

void setIO(string s){
    ios_base::sync_with_stdio(false); cin.tie(0);
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int MAXN = 1e5 + 1;

struct line{
    int m, c;
    line() {}
    line(int _m, int _c) : m(_m), c(_c) {}

    inline int calc(int x){
        return m * x + c;
    }

    inline long double x_int(line &other){
        return (long double)(c - other.c) / (other.m - m);
    }
};

int dp[MAXN], vel[MAXN], s[MAXN], d[MAXN], n, end_ = 0;
vector<pii> adj[MAXN];
line dq[MAXN];

inline int find_min(int x){
    int lo = 0, hi = end_ - 1, ret = 0, mid;
    while(hi >= lo){
        mid = lo + (hi - lo) / 2;
        if(mid + 1 < end_ && dq[mid].x_int(dq[mid + 1]) <= x){
            lo = mid + 1;
            ret = mid;
        }
        else{
            hi = mid - 1;
        }
    }
    return dq[ret].calc(x);
}

inline int removel(line &l){
    if(end_ < 2 || l.x_int(dq[end_ - 1]) >= dq[end_ - 1].x_int(dq[end_ - 2])){
        return end_;
    }

    int lo = 1, hi = end_ - 1, mid;
    while(hi > lo){
        mid = lo + (hi - lo) / 2;
        if(l.x_int(dq[mid]) < dq[mid].x_int(dq[mid - 1])){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    return lo;
}

inline void dfs(int v = 0, int p = 0){
    int pend_, ppos;
    line pline;
    if(!v){
        dp[v] = 0;
        dq[end_++] = {0, 0};
    }
    else{
        dp[end_] = find_min(vel[v]) + d[v] * vel[v] + s[v];
        line temp(-d[v], dp[v]);
        pend_ = end_;
        ppos = end_ = removel(temp);
        pline = dq[end_];
        dq[end_++] = temp;
    }

    for(pii &u : adj[v]){
        if(u.fi == p) continue;
        d[u.fi] = d[v] + u.se;
        dfs(u.fi, v);
    }

    if(v){
        end_ = pend_;
        dq[ppos] = pline;
    }
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
    setIO("harbingers");
    cin >> n;
    int a, b, w;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b >> w;
        adj[--a].emplace_back(--b, w);
        adj[b].emplace_back(a, w);
    }
    for(int i = 1; i < n; i++){
        cin >> s[i] >> vel[i];
    }
    dfs();

    for(int i = 0; i < n; i++){
        cout << dp[i] << " ";
    }
    cout << "\n";
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void setIO(std::string)':
harbingers.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100