#include <bits/stdc++.h>
using namespace std;
#define int long long
using lint = long long;
using pint = pair<int, int>;
#define x first
#define y second
const int maxn = 300004;
int N1, N2, N;
vector<pint> g[maxn];
struct func {
priority_queue<int> neg;
priority_queue<int, vector<int>, greater<int> > pos;
lint mn = 0;
void add(int x, int y, int z) {
neg.push(x);
pos.push(y);
mn += z;
while (neg.top() > pos.top()) {
int x = neg.top(), y = pos.top();
neg.pop(); pos.pop();
pos.push(x); neg.push(y);
mn += x - y;
}
}
};
func dfs(int x) {
func f;
for (pint i : g[x]) {
int k = i.x, t = i.y;
func g = dfs(k);
if (k <= N1) f.add(g.neg.top() + t, g.pos.top() + t, g.mn);
else f.add(t, t, 0);
}
return f;
}
main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N1 >> N2;
N = N1 + N2;
for (int i=2; i<=N; i++) {
int x, y;
cin >> x >> y;
g[x].emplace_back(i, y);
}
dfs(1);
cout << dfs(1).mn << '\n';
}
Compilation message
fireworks.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Correct |
9 ms |
7416 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7416 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7420 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Correct |
9 ms |
7416 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7416 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
11 |
Correct |
9 ms |
7420 KB |
Output is correct |
12 |
Correct |
9 ms |
7416 KB |
Output is correct |
13 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7416 KB |
Output is correct |
4 |
Correct |
9 ms |
7416 KB |
Output is correct |
5 |
Correct |
9 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Correct |
9 ms |
7416 KB |
Output is correct |
8 |
Correct |
9 ms |
7416 KB |
Output is correct |
9 |
Correct |
9 ms |
7416 KB |
Output is correct |
10 |
Correct |
9 ms |
7416 KB |
Output is correct |
11 |
Correct |
9 ms |
7420 KB |
Output is correct |
12 |
Correct |
9 ms |
7416 KB |
Output is correct |
13 |
Incorrect |
9 ms |
7416 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |