/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI09_harbingers
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
bool debug;
int N;
vii adjlist[MAXV];
ll delay[MAXV], speed[MAXV], d[MAXV];
ll dp[MAXV];
void dfs0(int v, int pv, ll depth) {
d[v] = depth;
for(auto x : adjlist[v]) {
if(x.fst == pv) continue;
dfs0(x.fst, v, depth + (ll)x.snd);
}
}
int q[MAXV], qct;
double crossPoint(int v1, int v2) {
return ((double)dp[v2] - (double)dp[v1]) / ((double)d[v2] - (double)d[v1]);
}
int bs_DP(int v, int hct) {
if(hct==1) return q[0];
if(hct==2) return (crossPoint(q[0], q[1]) > (double) speed[v]) ? q[0] : q[1];
int lo = 0, hi = hct-1, mid = 0;
while(lo < hi) {
mid = (lo+hi)/2;
if(mid == hct-1 || mid == 0) {
lo = hi+1;
} else if(crossPoint(q[mid-1], q[mid]) > (double) speed[v]) {
hi = mid -1;
} else if(crossPoint(q[mid], q[mid+1]) < (double) speed[v]) {
lo = mid + 1;
} else {
lo = hi+1;
}
}
/// double confirm
while(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > (double) speed[v]) mid--;
while(mid+1<=hct-1 && crossPoint(q[mid], q[mid+1]) < (double) speed[v]) mid++;
return q[mid];
}
int bs_Hull(int v, int hct){
if(hct==0) return 0;
if(hct==1) return 1;
if(crossPoint(q[hct-2], q[hct-1]) < crossPoint(q[hct-1], v)) return hct;
int lo = 0, hi = hct-1, mid = 0;
while(lo < hi) {
mid = (lo+hi)/2;
if(mid==0 || mid == hct-1) {
lo = hi+1;
} if(crossPoint(q[mid-1], q[mid]) > crossPoint(q[mid], v)) {
hi = mid-1;
} else if(crossPoint(q[mid], q[mid+1]) <= crossPoint(q[mid], v)) {
lo = mid+1;
} else {
lo = hi+1;
}
}
/// double confirm
if(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > crossPoint(q[mid], v)) mid--;
if(mid+1<=hct-1 && crossPoint(q[mid], q[mid+1]) <= crossPoint(q[mid], v)) mid++;
return mid;
}
void dfs(int v, int pv, int hct) {
if(debug) {
cout << "work on " << v << endl;
for(int i=0; i< qct; i++) cout << q[i] << " ";
cout << endl;
}
dp[v] = delay[v] + speed[v] * d[v];
if(hct>0) {
int j = bs_DP(v, hct);
ll ndp = dp[v] + dp[j] - d[j] * speed[v];
dp[v] = min(dp[v], ndp);
}
if(debug) cout << v << " " << dp[v] << endl;
int hullReplace = -1;
if(v!=1) {
hullReplace = qct;
q[qct] = v; qct++;
hullReplace = bs_Hull(v, hct);
swap(q[qct-1], q[hullReplace]);
}
for(auto x : adjlist[v]) {
if(x.fst == pv) continue;
dfs(x.fst, v, hullReplace+1);
}
if(v!=1) {
swap(q[qct-1], q[hullReplace]);
qct--;
}
}
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
int i, j, k;
cin >> N ;
for(i=1;i<=N-1;i++) {
int a, b, c; cin >> a >> b >> c;
adjlist[a].pb(mp(b,c)); adjlist[b].pb(mp(a,c));
}
for(i=2;i<=N;i++) cin >> delay[i] >> speed[i];
dfs0(1,0,0LL);
if(debug) cout << "complete setup" << endl;
qct = 0;
dfs(1, 0, 0);
if(debug) cout << "complete calculation" << endl;
for(i =2; i<=N; i++) cout << dp[i] << " ";
cout << endl;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:146:12: warning: unused variable 'j' [-Wunused-variable]
146 | int i, j, k;
| ^
harbingers.cpp:146:15: warning: unused variable 'k' [-Wunused-variable]
146 | int i, j, k;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
3052 KB |
Output isn't correct |
| 3 |
Incorrect |
45 ms |
9196 KB |
Output isn't correct |
| 4 |
Incorrect |
85 ms |
12160 KB |
Output isn't correct |
| 5 |
Incorrect |
110 ms |
15132 KB |
Output isn't correct |
| 6 |
Incorrect |
130 ms |
17980 KB |
Output isn't correct |
| 7 |
Incorrect |
61 ms |
10092 KB |
Output isn't correct |
| 8 |
Incorrect |
171 ms |
13788 KB |
Output isn't correct |
| 9 |
Correct |
164 ms |
15468 KB |
Output is correct |
| 10 |
Incorrect |
142 ms |
14716 KB |
Output isn't correct |
