# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
580924 |
2022-06-22T06:24:53 Z |
반딧불(#8360) |
구슬과 끈 (APIO14_beads) |
C++17 |
|
887 ms |
62416 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
set<pair<int, ll> > link[200002];
ll ans;
pair<ll, int> maxRec[200002][2];
ll recFirst[200002];
map<pair<int, int>, pair<ll, ll> > mp; /// (p, x)
pair<ll, ll> dfs(int x, int p=-1, ll pLength=0){
ll maxAdd = maxRec[x][0].second == p ? maxRec[x][1].first : maxRec[x][0].first;
pair<ll, ll> ret (recFirst[x], -1);
vector<pair<ll, int> > delList;
for(auto py: link[x]){
int y = py.first;
if(y == p) continue;
pair<ll, ll> tmp = mp[make_pair(x, y)] = dfs(y, x, py.second);
ret.first += max(tmp.first, tmp.second+py.second);
recFirst[x] += max(tmp.first, tmp.second+py.second);
ll score = tmp.first + py.second - max(tmp.first, tmp.second+py.second);
maxAdd = max(maxAdd, score);
pair<ll, int> tp = make_pair(score, y);
if(maxRec[x][1] < tp){
maxRec[x][1] = tp;
if(maxRec[x][0] < tp) swap(maxRec[x][0], maxRec[x][1]);
}
delList.push_back(py);
// DP[x][0] += max(DP[y][0], DP[y][1] + py.second);
// maxAdd = max(maxAdd, DP[y][0] + py.second - max(DP[y][0], DP[y][1] + py.second));
}
for(auto y: delList) link[x].erase(y);
if(mp.find(make_pair(x, p)) != mp.end()){
auto it = mp.find(make_pair(x, p));
ret.first -= max(it->second.first, it->second.second + pLength);
}
ret.second = ret.first + maxAdd;
return ret;
}
ll solve(int root){
return dfs(root).first;
}
int main(){
scanf("%d", &n);
for(int i=1; i<n; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
link[x].insert(make_pair(y, z));
link[y].insert(make_pair(x, z));
}
for(int i=1; i<=n; i++) maxRec[i][0] = maxRec[i][1] = make_pair(-1e12, -1);
for(int i=1; i<=n; i++){
ans = max(ans, solve(i));
}
printf("%lld", ans);
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
beads.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9668 KB |
Output is correct |
4 |
Correct |
6 ms |
9804 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9652 KB |
Output is correct |
9 |
Correct |
7 ms |
9684 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9668 KB |
Output is correct |
4 |
Correct |
6 ms |
9804 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9652 KB |
Output is correct |
9 |
Correct |
7 ms |
9684 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
7 ms |
9684 KB |
Output is correct |
18 |
Correct |
6 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
7 ms |
9684 KB |
Output is correct |
22 |
Correct |
7 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9668 KB |
Output is correct |
4 |
Correct |
6 ms |
9804 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9652 KB |
Output is correct |
9 |
Correct |
7 ms |
9684 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
7 ms |
9684 KB |
Output is correct |
18 |
Correct |
6 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
7 ms |
9684 KB |
Output is correct |
22 |
Correct |
7 ms |
9684 KB |
Output is correct |
23 |
Correct |
16 ms |
10452 KB |
Output is correct |
24 |
Correct |
13 ms |
10580 KB |
Output is correct |
25 |
Correct |
15 ms |
10580 KB |
Output is correct |
26 |
Correct |
20 ms |
11476 KB |
Output is correct |
27 |
Correct |
26 ms |
11476 KB |
Output is correct |
28 |
Correct |
20 ms |
12244 KB |
Output is correct |
29 |
Correct |
18 ms |
12116 KB |
Output is correct |
30 |
Correct |
21 ms |
11836 KB |
Output is correct |
31 |
Correct |
29 ms |
12608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9668 KB |
Output is correct |
4 |
Correct |
6 ms |
9804 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
7 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9652 KB |
Output is correct |
9 |
Correct |
7 ms |
9684 KB |
Output is correct |
10 |
Correct |
6 ms |
9684 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9684 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
7 ms |
9684 KB |
Output is correct |
18 |
Correct |
6 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
7 ms |
9684 KB |
Output is correct |
22 |
Correct |
7 ms |
9684 KB |
Output is correct |
23 |
Correct |
16 ms |
10452 KB |
Output is correct |
24 |
Correct |
13 ms |
10580 KB |
Output is correct |
25 |
Correct |
15 ms |
10580 KB |
Output is correct |
26 |
Correct |
20 ms |
11476 KB |
Output is correct |
27 |
Correct |
26 ms |
11476 KB |
Output is correct |
28 |
Correct |
20 ms |
12244 KB |
Output is correct |
29 |
Correct |
18 ms |
12116 KB |
Output is correct |
30 |
Correct |
21 ms |
11836 KB |
Output is correct |
31 |
Correct |
29 ms |
12608 KB |
Output is correct |
32 |
Correct |
145 ms |
18684 KB |
Output is correct |
33 |
Correct |
144 ms |
18596 KB |
Output is correct |
34 |
Correct |
159 ms |
18616 KB |
Output is correct |
35 |
Correct |
811 ms |
46072 KB |
Output is correct |
36 |
Correct |
887 ms |
46080 KB |
Output is correct |
37 |
Correct |
813 ms |
46076 KB |
Output is correct |
38 |
Correct |
556 ms |
60268 KB |
Output is correct |
39 |
Correct |
523 ms |
56128 KB |
Output is correct |
40 |
Correct |
569 ms |
57460 KB |
Output is correct |
41 |
Correct |
699 ms |
62416 KB |
Output is correct |