Submission #793265

#	Time	Username	Problem	Language	Result	Execution time	Memory
793265		nonono	Harbingers (CEOI09_harbingers)	C++14	100 / 100	106 ms	20896 KiB

harbingers

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

const int mxN = 1e5 + 10;
const long long INF = 1e18;

struct Line {
    long long a, b;
};

struct operation {
    int pos, top;
    Line overwrite;
    operation(int _p, int _t, Line _o) {
        pos = _p; top = _t; overwrite = _o;
    }
};

long long eval(Line a, long long x) {
    return a.a * x + a.b;
}

bool bad(Line a, Line b, Line c) {
    return (long double) (b.b - a.b) / (a.a - b.a) >= (long double) (c.b - a.b) / (a.a - c.a);  
}

vector<operation> undoLst;
Line lines[mxN];
int n, top;
vector<vector<pair<int, int>>> adj(mxN);
long long S[mxN], V[mxN], h[mxN], dp[mxN];

long long get(long long coord) {
    int low = 0, high = top - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        long long x = eval(lines[mid], coord);
        long long y = eval(lines[mid + 1], coord);
        
        if(x >= y) low = mid + 1; else high = mid - 1;
    }
    
    return eval(lines[low], coord);
}

void insert_line(Line newLine) {
    int low = 1, high = top - 1, k = top;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(bad(lines[mid - 1], lines[mid], newLine)) {
            k = mid; high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    undoLst.push_back(operation(k, top, lines[k]));
    top = k + 1;
    lines[k] = newLine;
}

void undo() {
    operation ope = undoLst.back(); undoLst.pop_back();
    top = ope.top; lines[ope.pos] = ope.overwrite;
}

void dfs(int u, int par) {
    if(u > 1) {
        dp[u] = get(V[u]) + h[u] * V[u] + S[u]; 
    }
    
    insert_line({- h[u], dp[u]});
    for(auto [v, d] : adj[u]) {
        if(v == par) continue ;
        h[v] = h[u] + d;
        dfs(v, u);
    }
    
    undo();
}

signed main() {
    #define taskname ""

    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    for(int i = 1; i <= n - 1; i ++) {
        int u, v, d;
        cin >> u >> v >> d;
        
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    
    for(int i = 2; i <= n; i ++) cin >> S[i] >> V[i];
    dfs(1, 0);
        
    for(int i = 2; i <= n; i ++) cout << dp[i] << " ";
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [v, d] : adj[u]) {
      |              ^
harbingers.cpp: In function 'int main()':
harbingers.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100