Submission #346480

#TimeUsernameProblemLanguageResultExecution timeMemory
346480gmyuHarbingers (CEOI09_harbingers)C++14
0 / 100
166 ms26496 KiB
/* 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 const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions struct NODE { int x, y; int val; int visited; bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); } }; struct EDGE { int from, to; ll weight; bool operator<(EDGE other) const { return weight < other.weight; } }; 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(int v) { int lo = 0, hi = qct-1, mid = 0; while(lo < hi) { mid = (lo+hi)/2; if(debug) cout << "bs " << q[mid] << endl; if(mid == qct-1 || mid == 0) { lo = hi+1; } else if(crossPoint(q[mid-1], q[mid]) > speed[v]) { if(debug) cout << " .. hi goes down " << lo << " " << hi << endl; hi = mid -1; } else if(crossPoint(q[mid], q[mid+1]) < speed[v]) { if(debug) cout << " .. lo goes up " << lo << " " << hi << endl; lo = mid + 1; } else { if(debug) cout << " .. found " << q[mid] << endl; lo = hi+1; } } /// double confirm while(mid-1>=0 && crossPoint(q[mid-1], q[mid]) > speed[v]) mid--; while(mid+1<=qct-1 && crossPoint(q[mid], q[mid+1]) < speed[v]) mid++; return q[mid]; } void dfs(int v, int pv) { 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(qct>0) { int j; if(qct==1) { j = q[0]; } else if(qct==2) { j = q[0]; if(crossPoint(q[0], q[1]) < speed[v]) j = q[1]; } else { if(debug) cout << " .. go bs" << endl; j = bs(v); if(debug) cout << " .. bs find " << j; } ll ndp = dp[v] + dp[j] - d[j] * speed[v]; dp[v] = min(dp[v], ndp); } if(debug) cout << v << " " << dp[v] << endl; vi store; store.clear(); while(qct>=2 && crossPoint(qct-2, qct-1) > crossPoint(qct-1, v)) { store.pb(q[qct-1]); qct--; } q[qct] = v; qct++; for(auto x : adjlist[v]) { if(x.fst == pv) continue; dfs(x.fst, v); } qct--; for(int i = sz(store)-1; i>=0; i--) { q[qct] = store[i]; qct++; } store.clear(); } int main() { debug = false; ios_base::sync_with_stdio(false); cin.tie(0); int i, j, k; int ans = 0; 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); if(debug) cout << "complete calculation" << endl; for(i =2; i<=N; i++) cout << dp[i] << " "; }

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:145:12: warning: unused variable 'j' [-Wunused-variable]
  145 |     int i, j, k;
      |            ^
harbingers.cpp:145:15: warning: unused variable 'k' [-Wunused-variable]
  145 |     int i, j, k;
      |               ^
harbingers.cpp:146:9: warning: unused variable 'ans' [-Wunused-variable]
  146 |     int ans = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...