# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
159130 | 2019-10-21T06:28:07 Z | sealnot123 | Beads and wires (APIO14_beads) | C++14 | 205 ms | 24824 KB |
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; typedef long long LL; const int N=200005; LL dp[N][2], p[N]; vector<PII> g[N]; void DP(int u, int v){ int ch = 0; dp[u][1] = -1e18; LL b = -1e18; for(PII e: g[u]){ if(e.x == v) continue; DP(e.x, u); LL a = max(dp[e.x][0], dp[e.x][1]+e.y); dp[u][1] = max(dp[u][1]+a, dp[u][0]+dp[e.x][0]+e.y); dp[u][0] += a; p[e.x] = b; b = max(b, -a+dp[e.x][0]+e.y); } b = -1e18; for(int i = g[u].size()-1; i >= 0; i--){ PII e = g[u][i]; if(e.x == v) continue; p[e.x] = max(p[e.x], b); LL a = max(dp[e.x][0], dp[e.x][1]+e.y); b = max(b, -a+dp[e.x][0]+e.y); } } LL dfs(int u, int v, LL a, LL b, LL w){ LL X = max(0ll,max(a,b+w)); LL ans = dp[u][0]+X; //printf("%lld %lld %lld %lld %d\n", ans, a, b, w, u); for(PII e : g[u]){ if(e.x == v) continue; LL c = max(dp[e.x][0], dp[e.x][1]+e.y); LL A = dp[u][0]-c+X; LL B = dp[u][0]-c+max(p[e.x]+X, a+w); ans = max(ans, dfs(e.x, u, A, B, e.y)); } return ans; } int main(){ int i,j,k,l,a,b,c,d; int n; scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d%d",&a,&b,&c); g[a].push_back({b,c}); g[b].push_back({a,c}); } DP(1,1); //for(i=1;i<=n;i++) printf("%d %lld %lld %lld\n",i,dp[i][0],dp[i][1],p[i]); printf("%lld",dfs(1,1,-1e18,-1e18,0)); return 0; } /* 5 1 2 10 1 3 40 1 4 15 1 5 20 10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Correct | 6 ms | 4988 KB | Output is correct |
7 | Correct | 6 ms | 4984 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 7 ms | 4984 KB | Output is correct |
10 | Correct | 6 ms | 4984 KB | Output is correct |
11 | Correct | 6 ms | 4984 KB | Output is correct |
12 | Correct | 6 ms | 5060 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Correct | 6 ms | 4988 KB | Output is correct |
7 | Correct | 6 ms | 4984 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 7 ms | 4984 KB | Output is correct |
10 | Correct | 6 ms | 4984 KB | Output is correct |
11 | Correct | 6 ms | 4984 KB | Output is correct |
12 | Correct | 6 ms | 5060 KB | Output is correct |
13 | Correct | 6 ms | 5216 KB | Output is correct |
14 | Correct | 6 ms | 4984 KB | Output is correct |
15 | Correct | 6 ms | 4984 KB | Output is correct |
16 | Correct | 6 ms | 4984 KB | Output is correct |
17 | Correct | 6 ms | 5112 KB | Output is correct |
18 | Correct | 8 ms | 5112 KB | Output is correct |
19 | Correct | 7 ms | 5112 KB | Output is correct |
20 | Correct | 7 ms | 4984 KB | Output is correct |
21 | Correct | 6 ms | 4984 KB | Output is correct |
22 | Correct | 6 ms | 5112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Correct | 6 ms | 4988 KB | Output is correct |
7 | Correct | 6 ms | 4984 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 7 ms | 4984 KB | Output is correct |
10 | Correct | 6 ms | 4984 KB | Output is correct |
11 | Correct | 6 ms | 4984 KB | Output is correct |
12 | Correct | 6 ms | 5060 KB | Output is correct |
13 | Correct | 6 ms | 5216 KB | Output is correct |
14 | Correct | 6 ms | 4984 KB | Output is correct |
15 | Correct | 6 ms | 4984 KB | Output is correct |
16 | Correct | 6 ms | 4984 KB | Output is correct |
17 | Correct | 6 ms | 5112 KB | Output is correct |
18 | Correct | 8 ms | 5112 KB | Output is correct |
19 | Correct | 7 ms | 5112 KB | Output is correct |
20 | Correct | 7 ms | 4984 KB | Output is correct |
21 | Correct | 6 ms | 4984 KB | Output is correct |
22 | Correct | 6 ms | 5112 KB | Output is correct |
23 | Correct | 9 ms | 5496 KB | Output is correct |
24 | Correct | 9 ms | 5368 KB | Output is correct |
25 | Correct | 9 ms | 5368 KB | Output is correct |
26 | Correct | 13 ms | 5752 KB | Output is correct |
27 | Correct | 13 ms | 5752 KB | Output is correct |
28 | Correct | 12 ms | 5880 KB | Output is correct |
29 | Correct | 12 ms | 5752 KB | Output is correct |
30 | Correct | 11 ms | 5752 KB | Output is correct |
31 | Correct | 13 ms | 6136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Correct | 6 ms | 4988 KB | Output is correct |
7 | Correct | 6 ms | 4984 KB | Output is correct |
8 | Correct | 6 ms | 4984 KB | Output is correct |
9 | Correct | 7 ms | 4984 KB | Output is correct |
10 | Correct | 6 ms | 4984 KB | Output is correct |
11 | Correct | 6 ms | 4984 KB | Output is correct |
12 | Correct | 6 ms | 5060 KB | Output is correct |
13 | Correct | 6 ms | 5216 KB | Output is correct |
14 | Correct | 6 ms | 4984 KB | Output is correct |
15 | Correct | 6 ms | 4984 KB | Output is correct |
16 | Correct | 6 ms | 4984 KB | Output is correct |
17 | Correct | 6 ms | 5112 KB | Output is correct |
18 | Correct | 8 ms | 5112 KB | Output is correct |
19 | Correct | 7 ms | 5112 KB | Output is correct |
20 | Correct | 7 ms | 4984 KB | Output is correct |
21 | Correct | 6 ms | 4984 KB | Output is correct |
22 | Correct | 6 ms | 5112 KB | Output is correct |
23 | Correct | 9 ms | 5496 KB | Output is correct |
24 | Correct | 9 ms | 5368 KB | Output is correct |
25 | Correct | 9 ms | 5368 KB | Output is correct |
26 | Correct | 13 ms | 5752 KB | Output is correct |
27 | Correct | 13 ms | 5752 KB | Output is correct |
28 | Correct | 12 ms | 5880 KB | Output is correct |
29 | Correct | 12 ms | 5752 KB | Output is correct |
30 | Correct | 11 ms | 5752 KB | Output is correct |
31 | Correct | 13 ms | 6136 KB | Output is correct |
32 | Correct | 40 ms | 8824 KB | Output is correct |
33 | Correct | 41 ms | 8824 KB | Output is correct |
34 | Correct | 41 ms | 8824 KB | Output is correct |
35 | Correct | 191 ms | 20692 KB | Output is correct |
36 | Correct | 175 ms | 20716 KB | Output is correct |
37 | Correct | 203 ms | 20724 KB | Output is correct |
38 | Correct | 137 ms | 21052 KB | Output is correct |
39 | Correct | 141 ms | 21264 KB | Output is correct |
40 | Correct | 148 ms | 20960 KB | Output is correct |
41 | Correct | 205 ms | 24824 KB | Output is correct |