| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 581019 |
2022-06-22T08:22:43 Z |
박상훈(#8359) |
구슬과 끈 (APIO14_beads) |
C++17 |
|
1000 ms |
5460 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[200200];
int dp[200200][2];
void dfs(int s, int pa = -1, int w0 = 0){
int tmp = -1e9;
dp[s][0] = 0;
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]);
}
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);
}
vector<int> D;
for (int i=1;i<=n;i++) if (adj[i].size()==1) D.push_back(i);
int ans = 0;
for (auto i:D){
dfs(i);
ans = max(ans, dp[i][0]);
}
printf("%d\n", ans);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
beads.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 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 |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 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 |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4964 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 |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 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 |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4964 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 23 |
Correct |
239 ms |
5240 KB |
Output is correct |
| 24 |
Correct |
244 ms |
5240 KB |
Output is correct |
| 25 |
Correct |
236 ms |
5240 KB |
Output is correct |
| 26 |
Execution timed out |
1083 ms |
5460 KB |
Time limit exceeded |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 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 |
3 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4964 KB |
Output is correct |
| 22 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 23 |
Correct |
239 ms |
5240 KB |
Output is correct |
| 24 |
Correct |
244 ms |
5240 KB |
Output is correct |
| 25 |
Correct |
236 ms |
5240 KB |
Output is correct |
| 26 |
Execution timed out |
1083 ms |
5460 KB |
Time limit exceeded |
| 27 |
Halted |
0 ms |
0 KB |
- |
