제출 #641483

#제출 시각아이디문제언어결과실행 시간메모리
641483sumit_kk10Harbingers (CEOI09_harbingers)C++17
80 / 100
117 ms23476 KiB
#include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define pb push_back #define F first #define S second #define int long long using namespace std; const int N = 1e5 + 5, MOD = 1e9 + 7; vector<pair<int, int> > g[N]; int n, par[N], dis[N], dp[N], s[N], d[N]; struct Line{ int m, c; int val(int x){ return m*x + c; } }; vector<Line> hulls; int cur_hullsize; bool check(Line a, Line b, Line cc){ int x = (b.c - a.c); x = x * (a.m - cc.m); int y = (cc.c - a.c); y = y * (a.m - b.m); if(x > y) return true; return false; } int pos(int mm, int cc){ Line cur; cur.m = mm; cur.c = cc; if(cur_hullsize < 2) return cur_hullsize; int low = 1, high = cur_hullsize - 1, ans = cur_hullsize; while(low <= high){ int mid = (low + high) / 2; if(check(hulls[mid - 1], hulls[mid], cur)){ ans = mid; high = mid - 1; } else low = mid + 1; } return ans; } int get(int x){ if(!cur_hullsize) return (long long) LLONG_MAX; int low = 0, high = (int) cur_hullsize - 1, ans = (int) cur_hullsize - 1; while(low <= high){ int mid = (low + high) / 2; if(hulls[mid].val(x) <= hulls[mid + 1].val(x)){ ans = mid; high = mid - 1; } else low = mid + 1; } return hulls[ans].val(x); } void dfs(int node, int p, int sum){ dis[node] = sum; par[node] = p; for(auto k : g[node]){ if(k.F == p) continue; dfs(k.F, node, sum + k.S); } } /* we want to find the position in the convex hull where the current line will go we will replace that position with the current line we will change it back once I go up from that node */ void dfs1(int node){ int mn = s[node] + dis[node] * d[node]; int x = get(d[node]); if(x != LLONG_MAX) mn = min(mn, x + s[node] + dis[node] * d[node]); dp[node] = mn; int cur, here = cur_hullsize; Line pre; pre.m = 1; if(node != 1){ cur = cur_hullsize = pos(-dis[node], dp[node]); Line neww; neww.m = -dis[node]; neww.c = dp[node]; if(cur == hulls.size()) hulls.pb(neww); else{ pre = hulls[cur]; hulls[cur] = neww; } cur_hullsize++; } for(auto k : g[node]){ if(k.F == par[node]) continue; dfs1(k.F); } if(node != 1){ cur_hullsize = here; if(pre.m == 1) hulls.pop_back(); else hulls[cur] = pre; } } void solve(){ cin >> n; for(int i = 1; i < n; ++i){ int u, v, c; cin >> u >> v >> c; g[u].pb({v, c}); g[v].pb({u, c}); } for(int i = 1; i < n; ++i) cin >> s[i + 1] >> d[i + 1]; dfs(1, 0, 0); dfs1(1); for(int i = 2; i <= n; ++i) cout << dp[i] << " "; } int32_t main(){ fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }

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

harbingers.cpp: In function 'void dfs1(long long int)':
harbingers.cpp:96:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if(cur == hulls.size())
      |            ~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...