Submission #675488

#TimeUsernameProblemLanguageResultExecution timeMemory
675488AmirAli_H1Beads and wires (APIO14_beads)C++17
100 / 100
195 ms40848 KiB
// In the name of Allah #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define debug(x) cerr << #x << ": " << x << endl; #define kill(x) cout << x << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); int n; const int maxn = 2e5 + 5; const ll oo = 1e14; vector<pll> adj[maxn]; ll dp[maxn][2][2]; bool mark[maxn]; void dfs(int v, ll x = -1) { mark[v] = 1; ll res = 0; vector<pll> ls1, ls2, ls3; for (auto f : adj[v]) { auto [u, w] = f; if (!mark[u]) { dfs(u, w); res += dp[u][1][0]; ls1.pb(Mp(w + dp[u][0][0] - dp[u][1][0], u)); ls2.pb(Mp(w + dp[u][0][1] - dp[u][1][0], u)); ls3.pb(Mp(dp[u][1][1] - dp[u][1][0], u)); } } sort(all(ls1), greater<pll>()); sort(all(ls2), greater<pll>()); sort(all(ls3), greater<pll>()); if (x == -1 || len(ls1) < 1) { dp[v][1][0] = -oo; dp[v][1][1] = -oo; } else { dp[v][1][0] = max(-oo, res + x + ls1[0].F); dp[v][1][1] = max(-oo, res + x + ls2[0].F); } dp[v][0][0] = res; if (len(ls3) < 1) dp[v][0][1] = -oo; else dp[v][0][1] = max(-oo, res + ls3[0].F); if (len(ls1) >= 2) { dp[v][0][1] = max(dp[v][0][1], res + ls1[0].F + ls1[1].F); if (ls1[0].S != ls2[0].S) { dp[v][0][1] = max(dp[v][0][1], res + ls1[0].F + ls2[0].F); } else { dp[v][0][1] = max(dp[v][0][1], res + ls1[0].F + ls2[1].F); dp[v][0][1] = max(dp[v][0][1], res + ls1[1].F + ls2[0].F); } } dp[v][1][0] = max(dp[v][1][0], dp[v][0][0]); dp[v][1][1] = max(dp[v][1][1], dp[v][0][1]); ls1.clear(); ls1.shrink_to_fit(); ls2.clear(); ls2.shrink_to_fit(); ls3.clear(); ls3.shrink_to_fit(); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n - 1; i++) { int u, v; ll w; cin >> u >> v >> w; u--; v--; adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w)); } dfs(0); cout << max(dp[0][0][0], dp[0][0][1]) << endl; 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...