Submission #630053

#	Time	Username	Problem	Language	Result	Execution time	Memory
630053		MohamedFaresNebili	Harbingers (CEOI09_harbingers)	C++14	0 / 100	113 ms	42216 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

            const int LOG = 25;

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

            int 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;
            }

Compilation message (stderr)

harbingers.cpp: In function 'll solve(ll, ll, ll)':
harbingers.cpp:81:13: warning: no return statement in function returning non-void [-Wreturn-type]
   81 |             }
      |             ^
harbingers.cpp:79:36: warning: 'prev_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |                     hull[prev_pos] = prev_line;
      |                     ~~~~~~~~~~~~~~~^~~~~~~~~~~
harbingers.cpp:78:24: warning: 'prev_size' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |                     st = prev_size;
      |                     ~~~^~~~~~~~~~~

• Subtask 1: 0 / 100