Submission #1248180

#TimeUsernameProblemLanguageResultExecution timeMemory
1248180shiori_chanHarbingers (CEOI09_harbingers)C++20
60 / 100
71 ms25924 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second #define compact(v) v.erase(unique(all(v)) , v.end()) #define pi pair<int , int> #define vi vector<int> #define FOR(i , l , r) for(int i = l; i <= r; ++ i) using namespace std; typedef long long ll; #define int long long const int nd = 1e5 + 5; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> dist(1 , (int)2e9); struct line{ int a , b , p; line() : a(1e9) , b(0){} line(int a , int b) : a(a) , b(b){} int fx(int x) {return a * x + b;} int intersect(line d){ if(a == d.a){ if(d.b <= b) return -LONG_MAX; else return LONG_MAX; } return (d.b - b) / (a - d.a) + ((d.b - b) % (a - d.a) > 0); } } container[nd]; int SIZE = 0; struct node{ int pre_size , pos; line d; node(){} node(int _pre_size , int _pos , line _d): pre_size(_pre_size) , pos(_pos) , d(_d){} void recover(){ if(d.a == 1e9) return; container[pos] = d; SIZE = pre_size; } } persistent[nd]; void insert(line d , int r){ int top = SIZE - 1 , dow = 0 , pos = top + 1; while(top >= dow){ int mid = (top + dow) >> 1; if(container[mid].p >= container[mid].intersect(d)) top = mid - 1 , pos = mid; else dow = mid + 1; } persistent[r] = node(SIZE , pos , container[pos]); if(!pos) d.p = -LONG_MAX + 12012008; else d.p = container[pos - 1].intersect(d); SIZE = pos + 1 , container[pos] = d; } int get(int x){ int top = SIZE - 1 , dow = 0 , res = LONG_MAX; while(top >= dow){ int mid = (top + dow) >> 1; res = min(res , container[mid].fx(x)); if(container[mid].p > x) top = mid - 1; else dow = mid + 1; } return res; } vector <pi> adj[nd]; int depth[nd] , dp[nd] , v[nd] , s[nd]; void dfs(int r , int pre = 0){ if(r != 1) dp[r] = get(v[r]) + v[r] * depth[r] + s[r]; insert(line(-depth[r] , dp[r]) , r); for(auto [v , w] : adj[r]) if(v != pre){ depth[v] = w + depth[r]; dfs(v , r); } persistent[r].recover(); } void solve(){ int n; cin >> n; FOR(i , 2 , n){ int l , r , w; cin >> l >> r >> w; adj[l].pb({r , w}) , adj[r].pb({l , w}); } FOR(i , 2 , n) cin >> s[i] >> v[i]; memset(depth , 0 , sizeof(depth)); dfs(1); FOR(i , 2 , n) cout << dp[i] << " "; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #define task "task" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } solve(); return 0; } /* -. ::. -: .:::::::::: ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######: **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######: #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####: #####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####: ##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###: %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###: *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##: #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#: ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###. ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##: ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##. ###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##: ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%: ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########. ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########: :@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%%#: #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@ @#*+@*=##***##+*@###########: @*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########: @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%%##########: #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########: @%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########: =: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######: : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######: @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###: +@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%%: ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####: ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##. #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%%%#####. **@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########. ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########: -@@@ @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########: %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%%#=#*%###########: %@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########. @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########. @@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%. +@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%########### :%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######. :#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############. ++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@ @@.=@@@=*##*=@######%###### #%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%###### :@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%########## +-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@##### **%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%%#@###%+#=.@%########+%##### #@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@ :@@%%@####@**-:@%######%*#*###### @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%################# =%#######+@@##@#+*=@##%%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*###### .######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*###### .#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%##### :#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%##### @@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*#### #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####** ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##******** .#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###** #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+*** .####**%%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#************* ####*#%*#####+#@@ =@%%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#*********** .#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++ ######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#**** #####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++ ####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+ ##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@* .##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@ #+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . # *#****##%% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - ....... **++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:. ++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= ......... +######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:... ##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ...... ####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...:::: */

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:112:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...