제출 #723409

#제출 시각아이디문제언어결과실행 시간메모리
723409bLICHarbingers (CEOI09_harbingers)C++17
30 / 100
1093 ms65536 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define uniq(v) v.erase(unique(all(v)), v.end()) #define ft first #define sd second #define pb push_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;} ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);} template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } // use ?: with brackets (?:) // check for overflow // think about dp // Read the statement carefully struct Line{ ll m, c; Line(ll mm, ll cc):m(mm), c(cc){} Line(){} ll at(ll x){ return m*x+c; } friend ostream& operator<<(ostream&out, Line l){ out<<l.m<<"x + "<<l.c<<' '; return out; } }; double intersection(const Line& l1, const Line& l2) { return (l2.c-l1.c)/(double)(l1.m-l2.m); } #define sq(x) ((x)*(x)) const int maxN = 1e5+5; // change this const int maxK = 8001; ll dep[maxN]; ll dp[maxN]; ll V[maxN], S[maxN]; vii adj[maxN]; Line getline(int x, vector<pair<double, Line>>& d){ int l = 0, r = sz(d); while(r-l>1){ int m = (l+r)/2; if (d[m].first<=x) l = m; else r = m; } return d[l].second; } void dfs(int node, vector<pair<double, Line>>& d, int par = 0){ stack<pair<double, Line>> tmp; if (node==1){ dp[node] = 0; Line curr = {0, 0}; d.push_back({0, curr}); } else { dp[node] = V[node]*dep[node]+S[node] + getline((int)V[node], d).at(V[node]); Line curr(-dep[node], dp[node]); double intersect = intersection(curr, d.back().second); while(sz(d)>0 && intersect<=d.back().first) { tmp.push(d.back()); d.pop_back(); intersect = intersection(curr, d.back().second); } d.push_back({intersect, curr}); } for (pii x:adj[node]){ if (x.ft==par) continue; dep[x.ft] = dep[node] + x.sd; dfs(x.first, d, node); } d.pop_back(); while(!tmp.empty()) d.push_back(tmp.top()), tmp.pop(); } void solve(){ int n;cin>>n; for (int i = 0;i<n-1;i++){ int u, v, w;cin>>u>>v>>w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for (int i = 2;i<=n;i++){ cin>>S[i]>>V[i]; } vector<pair<double, Line>> d; d.reserve(n+1); dfs(1, d); for (int i = 2;i<=n;i++) cout<<dp[i]<<' '; return; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define ONLINE_JUDGE #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); freopen("debug.dbg", "w", stderr); int tt = clock(); #endif int t=1, i = 1; // cin>>t; while(t--){ // cout<<"Case #"<<i++<<": "; solve(); cout<<"\n"[t!=0]; } #ifndef ONLINE_JUDGE cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl; tt = clock(); #endif }

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

harbingers.cpp: In function 'int main()':
harbingers.cpp:193:14: warning: unused variable 'i' [-Wunused-variable]
  193 |     int t=1, i = 1;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...