Submission #1143396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143396		aboeldahab	Harbingers (CEOI09_harbingers)	C++20	90 / 100	121 ms	28232 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define Aboeldahab ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
// #define int long long
#define ld long double
#define all(x) x.begin(),x.end()
#define mem(x, y) memset(x,y,sizeof x)

#define endl '\n'

const int dx8[8] = {0, 0, 1, -1, 1, -1, -1, 1};
const int dy8[8] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
char direction[4] = {'r', 'l', 'd', 'u'};

void READFILE() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#endif
}


const int inf = 1e9 + 5, N = 1e5 + 5, M = 5e3 + 1, MAX_X = 2001, LG = 15, mod =
                1e9 + 7, p1 = 31, p2 = 37, SQ = 470;
const ll LLinf = 8e18;

struct PT {
    ll x, y;

    PT(ll x = 0, ll y = 0): x(x), y(y) {
    }

    friend ll dot(PT &a, PT &b) {
        return 1ll * a.x * b.x + 1ll * a.y * b.y;
    }

    friend int orientation(PT &a, PT &b, PT &c) {
        ll s = 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (b.y - a.y) * (c.x - a.x);
        return (s > 0) - (s < 0);
    }
};

struct PersistentCHT {
    //minimizes dot product
    const static int N = 1e5 + 5;
    const static int lg = 17;
    int p[N][lg], sz;
    PT pnt[N];

    int insert(PT a, int rt) {
        for (int u, v, i = lg - 1; i >= 0; i--)
            if ((u = p[rt][i]) && (v = p[u][0]) && orientation(pnt[v], pnt[u], a) <= 0)
                rt = u;
        if (p[rt][0] && orientation(pnt[p[rt][0]], pnt[rt], a) <= 0) rt = p[rt][0];
        pnt[++sz] = a;
        p[sz][0] = rt;
        for (int i = 1; i < lg; i++) p[sz][i] = p[p[sz][i - 1]][i - 1];
        return sz;
    }

    ll query(PT a, int rt) {
        for (int u, v, i = lg - 1; i >= 0; i--)
            if ((u = p[rt][i]) && (v = p[u][0]) && dot(a, pnt[v]) > dot(a, pnt[u]))
                rt = u;
        if (p[rt][0] && dot(a, pnt[p[rt][0]]) > dot(a, pnt[rt])) rt = p[rt][0];
        return rt ? dot(a, pnt[rt]) : -1e18;
    }
} cht;


vector<pair<int, ll> > adj[N], Harbingers(N);
ll dist[N], dp[N];
int root[N];

void dfs(int node, int p = 0) {
    if (node) {
        dp[node] = Harbingers[node].first + Harbingers[node].second * dist[node];
        dp[node] -= cht.query(PT(Harbingers[node].second, -1), root[p]);
    }
    root[node] = cht.insert(PT(dist[node], dp[node]), root[p]);
    for (auto [v,w]: adj[node]) {
        if (v == p) continue;
        dist[v] = dist[node] + w;
        dfs(v, node);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        u--, v--;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    for (int i = 1; i < n; ++i) {
        int s, v;
        cin >> s >> v;
        Harbingers[i] = {s, v};
    }
    dfs(0);
    for (int i = 1; i < n; ++i) cout << dp[i] << " ";
}

signed main() {
    //READFILE();
    Aboeldahab
    int tc = 1;
    // cin >> tc;

    while (tc--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 90 / 100