제출 #506130

#제출 시각아이디문제언어결과실행 시간메모리
506130codebuster_10Harbingers (CEOI09_harbingers)C++17
10 / 100
1101 ms31156 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t //be careful about this #define pr pair #define ar array #define f first #define s second #define vt vector #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define SZ(x) ((int)(x).size()) #define all(a) (a).begin(),(a).end() #define allr(a) (a).rbegin(),(a).rend() #define mem(a,b) memset(a, b, sizeof(a)) template<class A> void rd(vt<A>& v); template<class T> void rd(T& x){ cin >> x;} template<class H, class... T> void rd(H& h, T&... t) { rd(h); rd(t...);} template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a);} template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;} template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;} template<typename T> void __p(T a) { cout<<a; } template<typename T, typename F> void __p(pair<T, F> a) { cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<typename T> void __p(std::vector<T> a) { cout<<"{"; for(auto it=a.begin(); it<a.end(); it++) __p(*it),cout<<",}\n"[it+1==a.end()]; } template<typename T, size_t N> void __p(array<T,N> a){ cout<<"{"; for(int i = 0; i < N; ++i) __p(a[i]),cout<<",}\n"[i+1==N]; } template<typename T, typename ...Arg> void __p(T a1, Arg ...a) { __p(a1); __p(a...); } template<typename Arg1> void __f(const char *name, Arg1 &&arg1) { cout<<name<<" : "; __p(arg1); cout<<endl; } template<typename Arg1, typename ... Args> void __f(const char *names, Arg1 &&arg1, Args &&... args) { int bracket=0,i=0; for(;; i++) if(names[i]==','&&bracket==0) break; else if(names[i]=='(') bracket++; else if(names[i]==')') bracket--; const char *comma=names+i; cout.write(names,comma-names)<<" : "; __p(arg1); cout<<" | "; __f(comma+1,args...); } #define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__) void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); cout.precision(20); cout << fixed; if(SZ(s)){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } const auto start_time = std::chrono::high_resolution_clock::now(); void output_run_time(){ // will work for ac,cc&&cf. #ifndef ONLINE_JUDGE auto end_time = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> diff = end_time-start_time; cout << "\n\n\nTime Taken : " << diff.count(); #endif } /*/--------------------------------------------------look below-----------------------------------------------------------------------------------/*/ /* * Description :- monotonic convex hull trick. * Source :- https://codeforces.com/blog/entry/63823. * Verf :- DMOJ APIO 10' 1. */ // F = true means queries are in arbitary order else they are in non-increasing order. // add(m,c) has m in non-increasing order. // return max value for m*x+c. template<bool F> struct monotonic_cht{ static int floor_div(int a,int b){ return a/b-((a^b)<0&&a%b); } struct line{ int m,c; int eval(int x){ return m*x+c; } long double isect(const line& l){ return (c-l.c)/(l.m-m); } }; deque<line> dq; void init(){ dq.clear(); } vector<vector<line>> change; void add(int m,int c){ line cur = {m,c}; vector<line> rem; if(dq.size() >= 1 && dq.front().m == m){ if(dq.front().c >= c){ change.pb(rem);return; } rem.pb(dq.front()); dq.pop_front(); } while(dq.size() >= 2 && cur.isect(dq[0]) >= dq[0].isect(dq[1])) rem.pb(dq.front()),dq.pop_front(); dq.push_front(cur); change.pb(rem);return; } void roll_back(){ dq.pop_front(); auto rem = change.back(); change.pop_back(); reverse(all(rem)); for(auto l : rem) dq.push_front(l); return; } int query(int x){ if(F){ assert(!dq.empty()); if(dq.size() == 1 || dq[0].isect(dq[1]) > x) return dq[0].eval(x); int lo = 0, hi = dq.size() - 1; while(hi - lo > 1){ int mid = (hi + lo)/2; dq[mid].isect(dq[mid+1]) < (long double)x ? lo = mid : hi = mid; } return dq[lo+1].eval(x); }else{ while(dq.size() >= 2 && end(dq)[-1].eval(x) <= end(dq)[-2].eval(x)) dq.pop_back(); return dq.back().eval(x); } } }; signed main(){ setIO(); int n; rd(n); vt<vt<pr<int,int>>> g(n); for(int e = 0; e < n-1; ++e){ int u,v,w; rd(u,v,w); --u,--v; g[u].eb(v,w); g[v].eb(u,w); } vt<int> p(n,0),s(n,0); for(int i = 1; i < n; ++i) rd(p[i],s[i]); monotonic_cht<true> cht; vt<int> t(n); int offset = 0; t[0] = 0; cht.add(0,0); function<void(int,int)> dfs = [&](int i,int par)->void{ for(auto [j,w] : g[i]) if(j != par){ t[j] = p[j] + w * s[j] - cht.query(-s[j]) + offset * s[j]; cht.add(-offset-w,-t[j]); offset += w; dfs(j,i); cht.roll_back(); offset -= w; } }; dfs(0,-1); for(int i = 1; i < n; ++i) cout << t[i] << " "; //output_run_time(); return 0; } // tips to avoid bugs. /* * be careful of whats happening you dont want a continue statement to miss imp line of code. * be careful when to update what since it might be needed in next segment of code. * dont get stuck on one idea. * dont use too much space bar so that code is written quickly as possible. */

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

harbingers.cpp: In function 'void setIO(std::string)':
harbingers.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...