# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
15854 | myungwoo | Beads and wires (APIO14_beads) | C++14 | 1068 ms | 10112 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |