Submission #15854

#TimeUsernameProblemLanguageResultExecution timeMemory
15854myungwooBeads and wires (APIO14_beads)C++14
28 / 100
1068 ms10112 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) int N; int D[MAXN], E[MAXN]; int up[MAXN], V[MAXN]; vector <int> con[MAXN], conv[MAXN]; void dfs(int n, int from) { vector <int> arr; for (int i=sz(con[n]);i--;){ int t = con[n][i], v = conv[n][i]; if (t == from) continue; up[t] = v; dfs(t, n); arr.pb(t); } D[n] = E[n] = 0; for (int t: arr){ V[t] = max(D[t], E[t]); D[n] += V[t]; } for (int t: arr){ E[n] = max(E[n], D[n] - V[t] + D[t] + up[t] + up[n]); } } int main() { scanf("%d", &N); for (int i=1;i<N;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[a].pb(b); conv[a].pb(c); con[b].pb(a); conv[b].pb(c); } int ans = 0; for (int i=1;i<=N;i++){ dfs(i, 0); ans = max(ans, D[i]); } printf("%d\n", ans); }

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...