Submission #42021

#TimeUsernameProblemLanguageResultExecution timeMemory
42021cmasterBeads and wires (APIO14_beads)C++14
0 / 100
12 ms12032 KiB
#include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp>*/ #define pb push_back #define mp make_pair #define sz(s) ((int)(s.size())) #define all(s) s.begin(), s.end() #define rep(i, a, n) for (int i = a; i <= n; ++i) #define per(i, n, a) for (int i = n; i >= a; --i) #define onlycin ios_base::sync_with_stdio(false); cin.tie(0) #define F first #define S second using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; /*typedef tree< pair < int, int >, null_type, less< pair < int, int > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;*/ // find_by_order() order_of_key() const int MAXN = (int)5e5+228; const char nxtl = '\n'; const int mod = (int)1e9+7; const double eps = (double)1e-7; template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} int n, dp[2][MAXN]; vector < pair < int, int > > g[MAXN]; void dfs(int v, int D = 0, int pr = -1) { dp[0][v] = dp[1][v] = 0; vector < pair < int, int > > child; for(auto &it : g[v]) { int to = it.F; if(pr == to) continue; dfs(to, it.S, v); child.pb({to, it.S}); } // update dp[1] if(pr != -1) { int sum0 = 0; for(auto &to : child) sum0 += max(dp[0][to.F], dp[1][to.F]); for(auto &to : child) { sum0 -= max(dp[0][to.F], dp[1][to.F]); updmax(dp[1][v], sum0+D+to.S+dp[0][to.F]); sum0 += max(dp[0][to.F], dp[1][to.F]); } } // update dp[0] for(auto &to : child) { for(auto &it : child) { if(to.F == it.F) continue; int sum = 0; for(auto &k : child) { if(k.F == to.F || k.F == it.F) continue; sum += max(dp[0][k.F], dp[1][k.F]); } updmax(dp[0][v], sum + to.S + it.S + dp[0][to.F] + dp[0][it.F]); } } cerr << v << ' '<< dp[0][v] << ' '<< dp[1][v] << nxtl; } int main() { #ifdef accepted freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif onlycin; cin >> n; rep(i, 2, n) { int x, y, z; cin >> x >> y >> z; g[x].pb(mp(y, z)); g[y].pb(mp(x, z)); } dfs(1); int res = dp[0][1]; rep(root, 2, n) { dfs(root); updmax(res, dp[0][root]); } cout << res << nxtl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...