Submission #630059

#	Time	Username	Problem	Language	Result	Execution time	Memory
630059		MohamedFaresNebili	Harbingers (CEOI09_harbingers)	C++14	100 / 100	137 ms	23468 KiB

harbingers

#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
            #define int ll

            struct Line{
                int m, c;
                Line(int m = 0, int c = 0) : m(m), c(c) {}
                int calc(int x) { return m * x + c; }
            };

            ld intX(Line A, Line B) {
                return (ld)(B.c - A.c) / (ld)(A.m - B.m);
            }

            int N, S[100005], V[100005], DP[100005];
            vector<array<int, 2>> adj[100005];

            Line hull[100005]; int st = 0;

            int query(int v) {
                int lo = 0, hi = st - 1;
                while(lo < hi) {
                    int md = (lo + hi) / 2;
                    if(intX(hull[md], hull[md + 1]) < v)
                        lo = md + 1;
                    else hi = md;
                }
                return hull[lo].calc(v);
            }
            int update(Line i) {
                if(st < 2 || intX(i, hull[st - 1]) >= intX(hull[st - 1], hull[st - 2]))
                    return st;
                int lo = 1, hi = st - 1;
                while(lo < hi) {
                    int md = (lo + hi) / 2;
                    if(intX(i, hull[md]) < intX(hull[md], hull[md - 1]))
                        hi = md;
                    else lo = md + 1;
                }
                return lo;
            }

            void solve(int v, int p, int d) {
                int prev_size, prev_pos;
                Line prev_line;
                if(v == 1) {
                    DP[v] = 0;
                    hull[st++] = {0, 0};
                }
                else {
                    DP[v] = query(S[v]) + d * S[v] + V[v];
                    Line i(-d, DP[v]);
                    prev_size = st;
                    prev_pos = st = update(i);

                    prev_line = hull[st];
                    hull[st++] = i;
                }

                for(auto u : adj[v]) {
                    if(u[0] == p) continue;
                    solve(u[0], v, d + u[1]);
                }

                if(v != 1) {
                    st = prev_size;
                    hull[prev_pos] = prev_line;
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N; memset(DP, -1, sizeof DP);
                for(int l = 0; l < N - 1; l++) {
                    int U, V, C; cin >> U >> V >> C;
                    adj[U].push_back({V, C});
                    adj[V].push_back({U, C});
                }
                for(int l = 2; l <= N; l++)
                    cin >> V[l] >> S[l];

                solve(1, 1, 0);

                for(int l = 2; l <= N; l++)
                    cout << DP[l] << " ";
                return 0;
            }

• Subtask 1: 100 / 100