# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
158433 | 2019-10-17T04:14:00 Z | mhy908 | 구슬과 끈 (APIO14_beads) | C++14 | 7 ms | 4984 KB |
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define mp make_pair #define inf 1987654321 using namespace std; typedef long long LL; int n; LL dp1[200010], dp2[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]+dp2[link[num][i].F]+link[num][i].S); } 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(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, -inf); printf("%lld", dp[1]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Incorrect | 7 ms | 4984 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Incorrect | 7 ms | 4984 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Incorrect | 7 ms | 4984 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Incorrect | 7 ms | 4984 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |