oj.uz

Submission #562543

# Submission time Handle Problem Language Result Execution time Memory
562543 2022-05-14T15:05:21 Z hoanghq2004 Harbingers (CEOI09_harbingers) C++14
100 / 100
 203 ms 28268 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

const int N = 1e5 + 10;

int n;
vector <pair <int, int> > g[N];
long long f[N];
int s[N], v[N], d[N];
struct Line {
    long long a, b;
    Line() {
        a = 0, b = 1e18;
    }
    Line(long long a, long long b): a(a), b(b) {};
    long long operator()(long long x) {
        return a * x + b;
    }
};

struct PersistentConvexHullTrick {
    Line convex[N];
    int bad(Line L1, Line L2, Line L3) {
        return 1.0L * (L2.b - L1.b) / (L1.a - L2.a) >= 1.0L * (L3.b - L1.b) / (L1.a - L3.a);
    }
    int par[N][20];
    void add(int u, int v, Line L) {
        for (int i = 19; i >= 0; --i)
            if (par[par[u][i]][0] && bad(convex[par[par[u][i]][0]], convex[par[u][i]], L)) u = par[u][i];
        while (par[u][0] && bad(convex[par[u][0]], convex[u], L)) u = par[u][0];
        convex[v] = L;
        par[v][0] = u;
        for (int i = 1; i < 20; ++i) par[v][i] = par[par[v][i - 1]][i - 1];
    }
    long long get(int u, long long x) {
        for (int i = 19; i >= 0; --i)
            if (par[par[u][i]][0] && convex[par[par[u][i]][0]](x) < convex[par[u][i]](x)) u = par[u][i];
        return min(convex[u](x), convex[par[u][0]](x));
    }
} DS;

void dfs(int u, int p) {
    f[u] = (u == 1 ? 0 : DS.get(p, v[u]) + 1LL * d[u] * v[u] + s[u]);
    DS.add(p, u, {- d[u], f[u]});
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
    dfs(1, 0);
    for (int i = 2; i <= n; ++i) cout << f[i] << " \n"[i == n];
}

Compilation message

harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [v, w]: g[u]) {
      |               ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 5 ms 4904 KB Output is correct
3 Correct 66 ms 14540 KB Output is correct
4 Correct 101 ms 19052 KB Output is correct
5 Correct 99 ms 23908 KB Output is correct
6 Correct 134 ms 28268 KB Output is correct
7 Correct 88 ms 18028 KB Output is correct
8 Correct 171 ms 24352 KB Output is correct
9 Correct 203 ms 25808 KB Output is correct
10 Correct 163 ms 24636 KB Output is correct