Submission #1166044

#TimeUsernameProblemLanguageResultExecution timeMemory
1166044Sang구슬과 끈 (APIO14_beads)C++20
100 / 100
77 ms28340 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--) #define fi first #define se second #define pb push_back #define ALL(a) (a).begin(), (a).end() #define task "kbsiudthw" typedef vector<int> vi; typedef pair<int, int> ii; typedef pair<int, ii> pii; const int N = 2e5 + 5; const int INF = 1e18; const int MOD = 1e9 + 2277; int n, dp[N][2][2], e[N]; vector<ii> G[N]; void dfs(int u, int par){ int f = -INF, s = -INF, f2 = -INF, s2 = -INF, best = -INF; int id1 = -1, id2 = -1, id3 = -1, id4 = -1, tot = 0; for (ii &v : G[u]){ if (v.fi == par) continue; e[v.fi] = v.se; dfs(v.fi, u); int nor = max(dp[v.fi][0][0], dp[v.fi][1][0]); tot += nor; best = max(best, max(dp[v.fi][0][1], dp[v.fi][1][1]) - nor); int d = dp[v.fi][0][1] + v.se - nor; if (d > f){ s = f; id2 = id1; f = d; id1 = v.fi; } else if (d > s){ s = d; id2 = v.fi; } int d2 = dp[v.fi][0][0] + v.se - nor; if (d2 > f2){ s2 = f2; id4 = id3; f2 = d2; id3 = v.fi; } else if (d2 > s2){ s2 = d2; id4 = v.fi; } } dp[u][0][0] = tot; dp[u][0][1] = max(tot + max(0ll, best), tot + f2 + s2); if (id1 != id3){ dp[u][0][1] = max(dp[u][0][1], tot + f + f2); } else { dp[u][0][1] = max(dp[u][0][1], tot + max(f + s2, f2 + s)); } dp[u][1][0] = tot + e[u] + f2; dp[u][1][1] = tot + e[u] + f; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n; FOR (i, 2, n){ int u, v, w; cin >> u >> v >> w; G[u].pb({v, w}); G[v].pb({u, w}); } dfs(1, 0); cout << max(dp[1][0][0], dp[1][0][1]); return 0; }

Compilation message (stderr)

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