# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
135097 | 2019-07-23T16:00:26 Z | wmrmr | Beads and wires (APIO14_beads) | C++17 | 15 ms | 14456 KB |
#include <bits/stdc++.h> using namespace std; const int MAX = 2e5+10, INF = 2e9+2; vector<int> g[MAX],id[MAX],w[MAX]; int dp[MAX][2]; int ans, r; void DFS(int v, int e) { int grau = g[v].size(); if(grau == 1) { if(e!=0) return; int prox = g[v][0], edge = id[v][0], peso = w[v][0]; DFS(prox,edge); dp[v][0] = dp[prox][0]; } int sum = 0; int big = -INF, bigger = -INF; for(int i=0;i<grau;i++) { int prox = g[v][i], edge = id[v][i], peso = w[v][i]; int dif; if(edge == e) dif = peso; else { DFS(prox,edge); sum += dp[prox][0]; dif = dp[prox][1] + peso - dp[prox][0]; } if(dif > bigger) { big = bigger; bigger = dif; } else if( dif > big ) big = dif; } dp[v][0] = max(sum,sum+big+bigger); big = -INF; bigger = -INF; for(int i=0;i<grau;i++) { int prox = g[v][i], edge = id[v][i], peso = w[v][i]; int dif; if(edge == e) continue; dif = dp[prox][1] + peso - dp[prox][0]; if(dif > bigger) { big = bigger; bigger = dif; } else if( dif > big ) big = dif; } dp[v][1] = max(sum,sum+big+bigger); return; } int main() { int n; scanf("%d",&n); for(int i=1;i<n;i++) { int a,b,c; scanf("%d %d %d",&a,&b,&c); g[a].push_back(b); g[b].push_back(a); id[a].push_back(i); id[b].push_back(i); w[a].push_back(c); w[b].push_back(c); } for(r=1;r<=n;r++) { if(g[r].size() == 1){ DFS(r,0); break; }; } printf("%d",dp[r][0]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 15 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Correct | 15 ms | 14456 KB | Output is correct |
5 | Correct | 15 ms | 14456 KB | Output is correct |
6 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 15 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Correct | 15 ms | 14456 KB | Output is correct |
5 | Correct | 15 ms | 14456 KB | Output is correct |
6 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 15 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Correct | 15 ms | 14456 KB | Output is correct |
5 | Correct | 15 ms | 14456 KB | Output is correct |
6 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 15 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Correct | 15 ms | 14456 KB | Output is correct |
5 | Correct | 15 ms | 14456 KB | Output is correct |
6 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |