Submission #672774

#TimeUsernameProblemLanguageResultExecution timeMemory
672774HanksburgerBeads and wires (APIO14_beads)C++17
100 / 100
304 ms79100 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; vector<pair<ll, ll> > adj[200005], child[200005]; ll f[200005][2], mx[200005], mx2[200005], ans; vector<ll> g[200005][2], h[200005][2]; pair<ll, ll> par[200005]; void dfs0(ll u) { for (ll i=0; i<adj[u].size(); i++) { int v=adj[u][i].first, w=adj[u][i].second; if (v==par[u].first) continue; par[v]={u, child[u].size()}; child[u].push_back({v, w}); dfs0(v); } } void dfs1(ll u) { // cout << "dfs " << u << '\n'; mx[u]=mx2[u]=-1e18; for (ll i=0; i<child[u].size(); i++) { ll v=child[u][i].first, w=child[u][i].second; dfs1(v); f[u][0]+=max(f[v][0], f[v][1]+w); ll z=f[v][0]+w-max(f[v][0], f[v][1]+w); if (mx[u]<=z) { mx2[u]=mx[u]; mx[u]=z; } else if (mx2[u]<z) mx2[u]=z; } f[u][1]=f[u][0]+mx[u]; // cout << "f[" << u << "][0] " << f[u][0] << '\n'; // cout << "f[" << u << "][1] " << f[u][1] << '\n'; for (ll i=0; i<child[u].size(); i++) { ll v=child[u][i].first, w=child[u][i].second; g[u][0].push_back(f[u][0]-max(f[v][0], f[v][1]+w)); if (mx[u]==f[v][0]+w-max(f[v][0], f[v][1]+w)) g[u][1].push_back(g[u][0][i]+mx2[u]); else g[u][1].push_back(g[u][0][i]+mx[u]); } } void dfs2(ll u) { // cout << "dfs2 " << u << '\n'; ll p=par[u].first, j=par[u].second; ll x=(u==1?0:child[p][j].second); for (ll i=0; i<child[u].size(); i++) { ll v=child[u][i].first, w=child[u][i].second; if (u==1) { h[u][0].push_back(g[u][0][i]); h[u][1].push_back(g[u][1][i]); } else { h[u][0].push_back(g[u][0][i]+max(h[p][0][j], h[p][1][j]+x)); h[u][1].push_back(max(g[u][0][i]+h[p][0][j]+x, g[u][1][i]+max(h[p][0][j], h[p][1][j]+x))); } ans=max(ans, f[v][0]+max(h[u][0][i], h[u][1][i]+w)); dfs2(v); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; for (ll i=1; i<n; i++) { ll u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs0(1); dfs1(1); dfs2(1); cout << max(ans, f[1][0]); }

Compilation message (stderr)

beads.cpp: In function 'void dfs0(long long int)':
beads.cpp:10:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (ll i=0; i<adj[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs1(long long int)':
beads.cpp:24:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (ll i=0; i<child[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
beads.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (ll i=0; i<child[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(long long int)':
beads.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (ll i=0; i<child[u].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...