# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
965242 | 2024-04-18T08:50:36 Z | hhnguyen | Harbingers (CEOI09_harbingers) | C++14 | 86 ms | 22612 KB |
#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; const int N = 1e5+5; typedef pair <ll,ll> ii; vector <ii> graph[N]; struct Line{ int m,c; int value(int x){ return m*x + c; } double intersect(Line D){ return ((c - D.c)/(D.m - m)); } }; ll n; ll V[N],S[N],dp[N],curr_sz = 0; Line L[N]; int min_val(int x){ int lo = 0; int hi = curr_sz-1; while(lo < hi){ int mid = (lo+hi)/2; if(L[mid].intersect(L[mid+1]) < x){ lo = mid+1; } else{ hi = mid; } } return L[lo].value(x); } int pos(Line D){ if(curr_sz <= 1 || D.intersect(L[curr_sz-1]) > L[curr_sz-1].intersect(L[curr_sz-2])){ return curr_sz; } int lo = 1; int hi = curr_sz-1; while(lo < hi){ int mid = (lo+hi)/2; if(D.intersect(L[mid]) < L[mid].intersect(L[mid-1])){ hi = mid; } else{ lo = mid+1; } } return lo; } void dfs(int src, int prev, int d){ for(auto [ch,dist] : graph[src]){ if(ch == prev) continue; dp[ch] = min_val(V[ch]) + V[ch]*(d+dist) + S[ch]; Line D = {-d-dist,dp[ch]}; int curr = curr_sz; int curr_pos = curr_sz = pos(D); Line pre = L[curr_pos]; L[curr_pos] = D; curr_sz++; dfs(ch,src,d+dist); //reset the changes L[curr_pos] = pre; curr_sz = curr; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n; for(ll i=1;i<n;i++) { ll a,b,c; cin >> a >> b >> c; graph[a].pb({b,c}); graph[b].pb({a,c}); } for(ll i=2;i<=n;i++){ cin >> S[i] >> V[i]; } L[0] = {0,0}; curr_sz++; dfs(1,-1,0); for(ll i=2;i<=n;i++){ cout << dp[i] << " "; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 5724 KB | Output is correct |
2 | Correct | 2 ms | 5980 KB | Output is correct |
3 | Incorrect | 26 ms | 12636 KB | Output isn't correct |
4 | Incorrect | 49 ms | 16212 KB | Output isn't correct |
5 | Incorrect | 54 ms | 19604 KB | Output isn't correct |
6 | Correct | 63 ms | 22612 KB | Output is correct |
7 | Incorrect | 37 ms | 12624 KB | Output isn't correct |
8 | Incorrect | 67 ms | 16780 KB | Output isn't correct |
9 | Incorrect | 86 ms | 18524 KB | Output isn't correct |
10 | Incorrect | 59 ms | 17092 KB | Output isn't correct |