Submission #520389

#TimeUsernameProblemLanguageResultExecution timeMemory
520389TAMREFBeads and wires (APIO14_beads)C++17
0 / 100
3 ms5032 KiB
#include <bits/stdc++.h> #define va first #define vb second #define lb lower_bound #define ub upper_bound #define bs binary_search #define pp push_back #define ep emplace_back #define all(v) (v).begin(),(v).end() #define szz(v) ((int)(v).size()) #define bi_pc __builtin_popcount #define bi_pcll __builtin_popcountll #define bi_tz __builtin_ctz #define bi_tzll __builtin_ctzll #define fio ios_base::sync_with_stdio(0);cin.tie(0); #ifdef TAMREF #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif using namespace std; using ll = long long; using lf = long double; using pii = pair<int,int>; using ppi = pair<int,pii>; using pll = pair<ll,ll>; using pff = pair<lf,lf>; using ti = tuple<int,int,int>; using base = complex<double>; const lf PI = 3.14159265358979323846264338L; template <typename T> inline T umax(T& u, T v){return u = max(u, v);} template <typename T> inline T umin(T& u, T v){return u = min(u, v);} mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mx = 2e5 + 5; ll up[mx], dp[mx]; vector<pii> G[mx]; bool vis[mx]; int n; void dfs(int x) { debug("dfs %d\n", x); priority_queue<pll> pq; vis[x] = 1; up[x] = -1e5; debug("healthy on %d, empty=%d\n", x, G[x].empty()); ll sum = 0; for(auto [u, w] : G[x]) { if(vis[u]) continue; dfs(u); sum += max(up[u] + w, dp[u]); debug("x = %d, u = %d, sum = %lld\n", x, u, sum); pq.emplace(min(dp[u] - up[u], ll(w)), u); } if(szz(pq)) { up[x] = max(sum, sum + pq.top().va); dp[x] = sum; } if(szz(pq) > 1) { auto [w1, u1] = pq.top(); pq.pop(); auto [w2, u2] = pq.top(); pq.pop(); debug("got alternator (%lld, %lld) and (%lld, %lld)\n", w1, u1, w2, u2); dp[x] = max(sum, sum + w1 + w2); } } int main(){ fio; cin >> n; if(n == 1) { cout << 0 << endl; return 0; } for(int i = 1, a, b, c; i < n; i++) { cin >> a >> b >> c; G[a].ep(b, c); G[b].ep(a, c); } dfs(1); cout << dp[1] << endl; }

Compilation message (stderr)

beads.cpp: In function 'void dfs(int)':
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:41:5: note: in expansion of macro 'debug'
   41 |     debug("dfs %d\n", x);
      |     ^~~~~
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:45:5: note: in expansion of macro 'debug'
   45 |     debug("healthy on %d, empty=%d\n", x, G[x].empty());
      |     ^~~~~
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:51:9: note: in expansion of macro 'debug'
   51 |         debug("x = %d, u = %d, sum = %lld\n", x, u, sum);
      |         ^~~~~
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:61:9: note: in expansion of macro 'debug'
   61 |         debug("got alternator (%lld, %lld) and (%lld, %lld)\n", w1, u1, w2, u2);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...