Submission #124151

#TimeUsernameProblemLanguageResultExecution timeMemory
124151youngyojunBeads and wires (APIO14_beads)C++11
100 / 100
294 ms33008 KiB
#include <bits/stdc++.h> #define eb emplace_back #define INFLL (0x3f3f3f3f3f3f3f3fll) using namespace std; typedef long long ll; const int MAXN = 200055; ll D[MAXN*2], E[MAXN*2]; ll MX[MAXN][2]; ll S[MAXN]; int O[MAXN*2]; bitset<MAXN*2> chk; vector<int> G[MAXN]; int cnt[MAXN]; int A[MAXN], B[MAXN], C[MAXN]; ll Ans; int N; int getC(int e) { return (e&1) ? N-cnt[B[e>>1]] : cnt[B[e>>1]]; } void dfs(int i) { cnt[i] = 1; for(int e : G[i]) { int v = A[e]^B[e]^i; if(cnt[v]) continue; dfs(v); cnt[i] += cnt[v]; } } int main() { ios::sync_with_stdio(false); cin >> N; for(int i = 0; i < N-1; i++) { cin >> A[i] >> B[i] >> C[i]; G[A[i]].eb(i); G[B[i]].eb(i); } dfs(1); for(int i = 0; i < N-1; i++) if(cnt[A[i]] < cnt[B[i]]) swap(A[i], B[i]); fill(MX[0], MX[N]+2, -INFLL); iota(O, O+(N-1)*2, 0); sort(O, O+(N-1)*2, [&](int a, int b) { return getC(a) < getC(b); }); for(int oi = 0, e, v, p; oi < (N-1)*2; oi++) { e = O[oi]; v = B[e>>1]; p = A[e>>1]; if(e&1) swap(v, p); chk[e] = true; D[e] = S[v] - (chk[e^1] ? max(D[e^1], E[e^1]) : 0); if(chk[e^1]) { ll t = -max(D[e^1], E[e^1]) + D[e^1] + C[e>>1]; E[e] = MX[v][0] == t ? MX[v][1] : MX[v][0]; } else E[e] = MX[v][0]; E[e] += D[e] + C[e>>1]; S[p] += max(D[e], E[e]); { ll t = -max(D[e], E[e]) + D[e] + C[e>>1]; if(MX[p][0] < t) swap(MX[p][0], t); if(MX[p][1] < t) swap(MX[p][1], t); } } for(int i = 1; i <= N; i++) { ll sum = 0; for(int e : G[i]) { int v = A[e]^B[e]^i; e = (e<<1) | (B[e] == i ? 1 : 0); sum += max(D[e], E[e]); } if(Ans < sum) Ans = sum; } cout << Ans << endl; return 0; }

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:76:8: warning: unused variable 'v' [-Wunused-variable]
    int v = A[e]^B[e]^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...