Submission #1269689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269689		i_elhdad	Harbingers (CEOI09_harbingers)	C++20	20 / 100	220 ms	131072 KiB

harbingers

//    #pragma GCC optimize ("O3")
//    #pragma GCC optimize ("unroll-loops")
//    #pragma comment(linker, "/STACK:2000000")
#include<bits/stdc++.h>

using namespace std;
#define ll long long
// #define int ll
#define ld long double
#define  ui unsigned int
#define endl "\n"
#define FOCUS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

void Go() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

// LLONG_MAX -> min f(x) , -LLONG_MAX -> max f(x)
// this min lichao
const ll DEFAULT = LLONG_MAX;
const ll INF = 1e9;
const int N = 1e9;

struct Line {
    ll m, c;

    Line(ll m = 0, ll c = DEFAULT) : m(m), c(c) {
    }

    ll operator()(ll x) const { return m * x + c; }
};
// this min lichao

struct Node {
    Node *left, *right;
    Line line;

    Node(Line line = Line(), Node *left = nullptr, Node *right = nullptr)
        : line(line), left(left), right(right) {
    }
};
// this min lichao

Node *insert(Line newLine, Node *root, ll l = -N, ll r = N) {
    if (root == nullptr) {
        return new Node(newLine, nullptr, nullptr);
    }
    Node *cur = new Node(root->line, root->left, root->right);
    ll m = l + (r - l) / 2;
    // (<) -> min f(x) , (>) -> max f(x)
    bool lef = newLine(l) < cur->line(l);
    bool mid = newLine(m) < cur->line(m);

    if (mid)
        swap(cur->line, newLine);
    if (r - l == 1)
        return cur;

    if (lef != mid)
        cur->left = insert(newLine, cur->left, l, m);
    else
        cur->right = insert(newLine, cur->right, m, r);
    return cur;
}

ll query(ll x, Node *cur, ll l = -N, ll r = N) {
    if (cur == nullptr)
        return DEFAULT;
    ll m = l + (r - l) / 2;
    if (r - l == 1)
        return cur->line(x);
        // min -> min f(x) , max -> max f(x)
    else if (x < m)
        return min(cur->line(x), query(x, cur->left, l, m));
    else
        return min(cur->line(x), query(x, cur->right, m, r));
}

vector<Node *> roots;
vector<vector<pair<int,int> > > adj;
vector<int> wait, speed;
vector<int> dp;
int n;

void solve(int node,int parent = -1,int dis = 0) {
    int &ret = dp[node];
    if (node) {
        int x = speed[node];
        ret = wait[node] + speed[node] * dis+ query(x, roots[parent]);
    }
    int m = -dis;
    int b = dp[node];
    Line temp = {m, b};
    Node *parentP = ((parent == -1) ? nullptr : roots[parent]);
    Node *cur = insert(temp, parentP);
    roots[node] = cur;
    for (auto [child,c]: adj[node]) {
        if (child == parent)continue;
        solve(child, node, dis + c);
    }
}

signed main() {
    FOCUS
    // Go();
    cin >> n;
    dp = vector<int>(n);
    adj = vector<vector<pair<int,int> > >(n);
    roots = vector<Node *>(n);
    roots[0] = nullptr;
    for (int i = 0; i < n - 1; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }

    wait = vector<int>(n);
    speed = vector<int>(n);
    for (int i = 1; i < n; i++) {
        cin >> wait[i] >> speed[i];
    }
    solve(0);
    for (int i = 1; i < n; i++) {
        cout << dp[i] << " ";
    }
}

Compilation message (stderr)

harbingers.cpp: In function 'void Go()':
harbingers.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100