Submission #1172666

#TimeUsernameProblemLanguageResultExecution timeMemory
1172666MinbaevPaths (RMI21_paths)C++20
12 / 100
74 ms30788 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define int long long #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; namespace FAST { template<typename T, typename F> istream &operator>>(istream &cin, pair<T, F> &p) { cin >> p.first >> p.second; return cin; } template<typename T, typename F> ostream &operator<<(ostream &cout, pair<T, F> &p) { cout << p.first << ' ' << p.second; return cout; } template<typename T> istream &operator>>(istream &cin, vector<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, vector<T> &a) { for (T i: a) cout << i << ' '; return cout; } template<typename T> istream &operator>>(istream &cin, deque<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, deque<T> &a) { for (T i: a) cout << i << ' '; return cout; } } using namespace FAST; const int inf = 3e18 + 7; const int mod = 1e9 + 7; const int N = 5e5 + 5; const int md = 998244353; int binpow(int a, int b, int m){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2,m); return (c*c)%m; } return (binpow(a,b-1,m)*a)%m; } int divi(int a, int b, int m){ return (a*(binpow(b,m-2, m)))%m; } int n,m,k,q; vector<int>sub(N), res(N); vector<ar<int,2>>g[N]; void dfs(int x, int pr){ for(auto [to, cost]:g[x]){ if(to == pr)continue; dfs(to, x); umax(sub[x], sub[to] + cost); } } void ans(int x, int pr, int val){ res[x] = max(sub[x], val); vector<ar<int,3>>vs; for(auto [to, cost]:g[x]){ if(to == pr)continue; vs.pb({sub[to] + cost, to, cost}); } sort(all(vs)); reverse(all(vs)); if(vs.size() == 1){ ans(vs[0][1], x, val + vs[0][2]); } else if(vs.size() > 1){ // if(x == 1){ // for(auto to:vs)cout << to[0] << " " << to[1] << " " << to[2] << "\n"; // } ans(vs[0][1], x, max(val + vs[0][2], vs[1][0] + vs[0][2])); for(int i = 1;i<vs.size();i++){ ans(vs[i][1], x, max(val + vs[i][2], vs[0][0] + vs[i][2])); } } } void solve(){ cin >> n >> m; for(int i = 2;i<=n;i++){ int a,b,c; cin >> a >> b >> c; g[a].pb({b, c}); g[b].pb({a, c}); } dfs(1, -1); ans(1, -1, 0); for(int i = 1;i<=n;i++){ cout << res[i] << "\n"; } } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...