# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
581058 |
2022-06-22T08:52:18 Z |
박상훈(#8359) |
구슬과 끈 (APIO14_beads) |
C++17 |
|
285 ms |
25040 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[200200];
int dp[200200][2], dp2[200200][2], par[200200], paw[200200];
void dfs(int s, int pa = -1, int w0 = 0){
int tmp = -1e9;
dp[s][0] = 0;
par[s] = pa;
paw[s] = w0;
for (auto &[v, w]:adj[s]) if (v!=pa){
dfs(v, s, w);
tmp = max(tmp, dp[v][0] + w - dp[v][1]);
dp[s][0] += dp[v][1];
}
if (w0+tmp>0) dp[s][1] = dp[s][0] + w0 + tmp;
else dp[s][1] = dp[s][0];
//if (C.size()>=2) dp[s][0] = max(dp[s][0], dp[s][0] + C[0] + C[1]);
//printf("%d: %d %d\n", s, dp[s][0], dp[s][1]);
}
void dfs2(int s, int pa = -1, int w0 = 0, int sum = 0, int mx = 0){
if (pa!=-1){
dp2[s][0] = sum - dp[s][1];
if (w0 + mx>0) dp2[s][1] = dp2[s][0] + w0 + mx;
else dp2[s][1] = dp2[s][0];
}
int ns = 0;
vector<int> nmx = {-1000000000, -1000000000};
for (auto &[v, w]:adj[s]) if (v!=pa){
ns += dp[v][1];
nmx.push_back(dp[v][0]+w - dp[v][1]);
}
if (pa!=-1){
ns += dp2[s][1];
nmx.push_back(dp2[s][0]+w0 - dp2[s][1]);
}
sort(nmx.begin(), nmx.end(), greater<int>());
for (auto &[v, w]:adj[s]) if (v!=pa){
if (nmx[0]!=dp[v][0]+w-dp[v][1]) dfs2(v, s, w, ns, nmx[0]);
else dfs2(v, s, w, ns, nmx[1]);
}
}
int calc(int s){
int ret1 = 0, ret2 = 0;
for (auto &[v, w]:adj[s]) if (v!=par[s]){
ret1 += dp[v][1];
}
if (par[s]!=-1) ret1 += dp2[s][1];
if (adj[s].size()<2) return ret1;
vector<int> V;
for (auto &[v, w]:adj[s]) if (v!=par[s]) V.push_back(dp[v][0]+w - dp[v][1]);
if (par[s]!=-1) V.push_back(dp2[s][0]+paw[s] - dp2[s][1]);
sort(V.begin(), V.end(), greater<int>());
ret2 = ret1 + V[0] + V[1];
return max(ret1, ret2);
}
int main(){
int n;
scanf("%d", &n);
for (int i=0;i<n-1;i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
adj[x].emplace_back(y, z);
adj[y].emplace_back(x, z);
}
dfs(1);
dfs2(1);
//for (int i=1;i<=n;i++) printf("%d: %d %d\n", i, dp[i][0], dp[i][1]);
//for (int i=1;i<=n;i++) printf("%d: %d %d\n", i, dp2[i][0], dp2[i][1]);
int ans = 0;
for (int i=1;i<=n;i++) ans = max(ans, calc(i));
printf("%d\n", ans);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
beads.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5004 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5008 KB |
Output is correct |
6 |
Correct |
4 ms |
5028 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5004 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5004 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5008 KB |
Output is correct |
6 |
Correct |
4 ms |
5028 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5004 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
4 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5004 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5004 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5008 KB |
Output is correct |
6 |
Correct |
4 ms |
5028 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5004 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
4 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5004 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
8 ms |
5280 KB |
Output is correct |
24 |
Correct |
6 ms |
5240 KB |
Output is correct |
25 |
Correct |
6 ms |
5332 KB |
Output is correct |
26 |
Correct |
13 ms |
5588 KB |
Output is correct |
27 |
Correct |
9 ms |
5608 KB |
Output is correct |
28 |
Correct |
8 ms |
5716 KB |
Output is correct |
29 |
Correct |
7 ms |
5588 KB |
Output is correct |
30 |
Correct |
8 ms |
5636 KB |
Output is correct |
31 |
Correct |
9 ms |
6228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5004 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5008 KB |
Output is correct |
6 |
Correct |
4 ms |
5028 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
4 ms |
5004 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
4 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5004 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
8 ms |
5280 KB |
Output is correct |
24 |
Correct |
6 ms |
5240 KB |
Output is correct |
25 |
Correct |
6 ms |
5332 KB |
Output is correct |
26 |
Correct |
13 ms |
5588 KB |
Output is correct |
27 |
Correct |
9 ms |
5608 KB |
Output is correct |
28 |
Correct |
8 ms |
5716 KB |
Output is correct |
29 |
Correct |
7 ms |
5588 KB |
Output is correct |
30 |
Correct |
8 ms |
5636 KB |
Output is correct |
31 |
Correct |
9 ms |
6228 KB |
Output is correct |
32 |
Correct |
39 ms |
8040 KB |
Output is correct |
33 |
Correct |
44 ms |
8052 KB |
Output is correct |
34 |
Correct |
45 ms |
8044 KB |
Output is correct |
35 |
Correct |
261 ms |
17248 KB |
Output is correct |
36 |
Correct |
285 ms |
17168 KB |
Output is correct |
37 |
Correct |
233 ms |
17080 KB |
Output is correct |
38 |
Correct |
158 ms |
19220 KB |
Output is correct |
39 |
Correct |
152 ms |
18596 KB |
Output is correct |
40 |
Correct |
173 ms |
18388 KB |
Output is correct |
41 |
Correct |
225 ms |
25040 KB |
Output is correct |