# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
158436 | 2019-10-17T04:21:28 Z | mhy908 | 구슬과 끈 (APIO14_beads) | C++14 | 7 ms | 5112 KB |
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define mp make_pair #define llinf 98765432198754321 #define inf 1987654321 using namespace std; typedef long long LL; int n; LL dp1[200010], dp2[200010], dp3[200010], dp[200010]; vector<pair<int, LL> > link[200010]; void get_dp(int num, int par, LL c) { LL sum=0; vector<LL> comp; for(int i=0; i<link[num].size(); i++){ if(par==link[num][i].F)continue; get_dp(link[num][i].F, num, link[num][i].S); sum+=dp[link[num][i].F]; comp.pb(-dp[link[num][i].F]+max(dp3[link[num][i].F], dp2[link[num][i].F])+link[num][i].S); dp3[num]=max(dp3[num], dp[link[num][i].F]); } sort(comp.begin(), comp.end(), greater<LL>()); if(comp.size()>=1)dp1[num]=sum+comp[0]+c; if(comp.size()>=2)dp2[num]=sum+comp[0]+comp[1]; dp[num]=max(dp3[num], max(dp1[num], dp2[num])); } int main() { scanf("%d", &n); for(int i=1; i<n; i++){ int a, b; LL c; scanf("%d %d %lld", &a, &b, &c); link[a].pb(mp(b, c)); link[b].pb(mp(a, c)); } get_dp(1, 0, -llinf); printf("%lld", max(dp2[1], dp3[1])); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5084 KB | Output is correct |
2 | Correct | 6 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Incorrect | 6 ms | 5112 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5084 KB | Output is correct |
2 | Correct | 6 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Incorrect | 6 ms | 5112 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5084 KB | Output is correct |
2 | Correct | 6 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Incorrect | 6 ms | 5112 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5084 KB | Output is correct |
2 | Correct | 6 ms | 5112 KB | Output is correct |
3 | Correct | 7 ms | 5112 KB | Output is correct |
4 | Incorrect | 6 ms | 5112 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |