Submission #520406

#TimeUsernameProblemLanguageResultExecution timeMemory
520406TAMREFBeads and wires (APIO14_beads)C++17
0 / 100
3 ms4940 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]; int vis[mx]; int n; ll dfs(int x) { // debug("dfs %d, vis = %d\n", x, vis[x]); set<pll> pq; up[x] = -1e5; dp[x] = 0; ll sum = 0; for(auto [u, w] : G[x]) { // debug("u = %d with vis = %d\n", u, vis[u]); if(vis[u] == vis[x]) continue; vis[u] = vis[x]; 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); while(szz(pq) > 2) pq.erase(pq.begin()); } if(szz(pq)) { up[x] = sum + pq.rbegin() -> va; dp[x] = sum; } if(szz(pq) > 1) { auto [w1, u1] = *pq.rbegin(); auto [w2, u2] = *next(pq.rbegin()); debug("got alternator (%lld, %lld) and (%lld, %lld)\n", w1, u1, w2, u2); dp[x] = max(sum, sum + w1 + w2); } debug("up[%d] = %lld, dp[%d] = %lld\n", x, up[x], x, dp[x]); return sum; } 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); } ll ans = 0; for(int i = 1; i <= n; i++) { vis[i] = i; ll lans = dfs(i); debug("i = %d, lans = %lld\n", i, lans); ans = max(ans, lans); } cout << ans << endl; }

Compilation message (stderr)

beads.cpp: In function 'll dfs(int)':
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:52:9: note: in expansion of macro 'debug'
   52 |         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:63:9: note: in expansion of macro 'debug'
   63 |         debug("got alternator (%lld, %lld) and (%lld, %lld)\n", w1, u1, w2, u2);
      |         ^~~~~
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:66:5: note: in expansion of macro 'debug'
   66 |     debug("up[%d] = %lld, dp[%d] = %lld\n", x, up[x], x, dp[x]);
      |     ^~~~~
beads.cpp: In function 'int main()':
beads.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beads.cpp:86:9: note: in expansion of macro 'debug'
   86 |         debug("i = %d, lans = %lld\n", i, lans);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...