제출 #346760

#제출 시각아이디문제언어결과실행 시간메모리
346760gmyuHarbingers (CEOI09_harbingers)C++14
10 / 100
167 ms17996 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 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++; if(mid==0) return 1; 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--; 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; }

컴파일 시 표준 에러 (stderr) 메시지

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