Submission #1196778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196778		Ghulam_Junaid	Harbingers (CEOI09_harbingers)	C++20	0 / 100	267 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 10;
int n;
int s[N], req[N], d[N];
ll dp[N];
vector<pii> g[N];
vector<pll> hull, del[N];

inline bool cmp(pll x, pll y){
    if ((x.F / x.S) != (y.F / y.S))
        return (x.F / x.S) > (y.F / y.S);
    x.F %= x.S;
    y.F %= y.S;
    return (x.F * y.S) > (y.F * x.S);
}

inline bool useful(pll &x, pll &y, pll &z){
    return cmp({x.S - y.S, y.F - x.F}, {y.S - z.S, z.F - y.F});
}

inline void insert(int v, pll L){
    while (hull.size() > 1 and !useful(hull[hull.size() - 2], hull.back(), L)){
        del[v].push_back(hull.back());
        hull.pop_back();
    }
    hull.push_back(L);
}

inline ll f(pll &L, int &x){
    return L.F * x + L.S;
}

ll ans, ans1, ans2;
int lo, hi, mid;
inline ll query(int x){
    ans = f(hull[0], x);
    lo = 0, hi = hull.size();
    while (hi - lo > 1){
        mid = (lo + hi) / 2;
        ans1 = f(hull[mid - 1], x);
        ans2 = f(hull[mid], x);

        if (ans1 < ans2){
            ans = ans1;
            hi = mid;
        }
        else{
            ans = ans2;
            lo = mid;
        }
    }
    return ans;
}

void dfs(int v, int p = -1){
    for (auto &[w, u] : g[v]){
        if (u == p) continue;
        d[u] = d[v] + w;
        
        dp[u] = query(-s[u]) + 1ll * s[u] * d[u] + req[u];
        insert(u, {d[u], dp[u]});

        dfs(u, v);
    }
    hull.pop_back();
    while (del[v].size())
        hull.push_back(del[v].back()), del[v].pop_back();
}

int main(){
    cin >> n;
    for (int i = 0; i < n - 1; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }
    for (int i = 2; i <= n; i ++)
        cin >> req[i] >> s[i];

    insert(1, {0, 0});
    dfs(1);
    for (int i = 2; i <= n; i ++)
        cout << dp[i] << " ";
    cout << endl;

    delete g;
    delete &hull;
    delete del;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:96:12: warning: deleting array 'g'
   96 |     delete g;
      |            ^
harbingers.cpp:98:12: warning: deleting array 'del'
   98 |     delete del;
      |            ^~~
harbingers.cpp:96:12: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'g' [-Wfree-nonheap-object]
   96 |     delete g;
      |            ^
harbingers.cpp:15:13: note: declared here
   15 | vector<pii> g[N];
      |             ^
harbingers.cpp:97:13: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'hull' [-Wfree-nonheap-object]
   97 |     delete &hull;
      |             ^~~~
harbingers.cpp:16:13: note: declared here
   16 | vector<pll> hull, del[N];
      |             ^~~~
harbingers.cpp:98:12: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'del' [-Wfree-nonheap-object]
   98 |     delete del;
      |            ^~~
harbingers.cpp:16:19: note: declared here
   16 | vector<pll> hull, del[N];
      |                   ^~~

• Subtask 1: 0 / 100