# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
135257 | 2019-07-23T21:45:18 Z | pedro_sponchiado | Beads and wires (APIO14_beads) | C++17 | 15 ms | 14456 KB |
#include<bits/stdc++.h> using namespace std; const int maxn=200000; const int INF=1000000000; int n; vector<int> adj[maxn], peso[maxn]; int dp1[maxn], dp2[maxn]; int marc[maxn]; vector<pair<int, int> > filhos[maxn]; vector<int> aux; void dfs(int u, int p_ar_ant){ marc[u]=1; int folha=1; for(int i=0; i<adj[u].size(); i++){ int v=adj[u][i]; if(marc[v]==0){ folha=0; dfs(v, peso[u][i]); filhos[u].push_back(make_pair(dp1[v]+peso[u][i], max(dp1[v], dp2[v]))); } } if(folha){ dp1[u]=0; dp2[u]=-INF; return; } int t=filhos[u].size(); int s=0; for(int i=0; i<t; i++) s+=filhos[u][i].second; //calcula dp1[u] if(t>=2){ dp1[u]=-INF; for(int i=0; i<t; i++){ for(int k=i+1; k<t; k++){ int aux1=s-filhos[u][i].second-filhos[u][k].second + filhos[u][i].first+filhos[u][k].first; dp1[u]=max(dp1[u], aux1); } } } else dp1[u]=s; //calcula dp2[u] if(p_ar_ant!=-1){ dp2[u]=-INF; for(int i=0; i<t; i++){ int aux1=s-filhos[u][i].second+filhos[u][i].first; dp2[u]=max(dp2[u], aux1); } dp2[u]+=p_ar_ant; } return; } int main(){ scanf("%d", &n); for(int a, b, p, i=1; i<=n-1; i++){ scanf("%d %d %d", &a, &b, &p); adj[a].push_back(b); adj[b].push_back(a); peso[a].push_back(p); peso[b].push_back(p); } dfs(1, -1); /* printf("\n\n"); for(int i=1; i<=n; i++){ printf("%d: %d %d\n", i, dp1[i], dp2[i]); } */ printf("%d\n", dp1[1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 14 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 14 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 14 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 14456 KB | Output is correct |
2 | Correct | 14 ms | 14456 KB | Output is correct |
3 | Correct | 14 ms | 14456 KB | Output is correct |
4 | Incorrect | 14 ms | 14456 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |