| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 401618 | BERNARB01 | Fireworks (APIO16_fireworks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct E {
long long x;
int e;
E(long long _x, int _e) {
x = _x;
e = _e;
}
bool operator<(const E& other) {
if (x == other.x) {
return e < other.e;
}
return x < other.x;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> g(n + m);
for (int i = 1; i < n + m; i++) {
int p;
long long c;
cin >> p >> c;
g[p - 1].emplace_back(i, c);
}
function<array<long long, 3>(int, long long)> DFS = [&](int u, long long val) {
array<long long, 3> ret = {0, -1, -1};
if (u && g[u].size() == 0) {
ret = {0, val, val};
return ret;
}
vector<E> events;
for (pair<int, long long> _p : g[u]) {
int v = _p.first;
long long w = _p.second;
if (v != p) {
array<long long, 3> sub = DFS(v, w);
ret[0] += sub[0];
events.push_back(E(sub[1], 0));
events.push_back(E(sub[2], 1));
}
}
assert(!events.empty());
sort(events.begin(), events.end());
vector<long long> D(events.size());
D[events.size() - 1] = 0;
long long add = 0, len = 0;
for (int i = (int) events.size() - 2; i >= 0; i--) {
len = events[i + 1].x - events[i].x;
D[i] = D[i + 1] + add * len;
add += !events[i].e;
}
long long dist = 0, minDist = (long long) D[0];
add = 0, len = 0;
for (int i = 0; i < (int) events.size(); i++) {
len = events[i].x - (i ? events[i - 1].x : events[i].x);
dist += add * len;
minDist = min(minDist, dist + D[i]);
//cout << dist << " ";
add += events[i].e;
}
//cout << '\n';
ret[0] += minDist;
add = 0, len = 0;
//for (const auto& x : events) {
//cout << x.x << " ";
//}
//cout << '\n';
//for (const auto& x : events) {
//cout << x.e << " ";
//}
//cout << '\n';
//for (const auto& x : D) {
//cout << x << " ";
//}
//cout << '\n';
//cout << minDist << '\n';
add = 0; len = 0; dist = 0;
for (int i = 0; i < (int) events.size(); i++) {
len = events[i].x - (i ? events[i - 1].x : events[i].x);
dist += add * len;
long long curDist = dist + D[i];
//cout << curDist << " ";
if (curDist == minDist && ret[1] == -1) {
ret[1] = events[i].x;
}
if (ret[1] != -1 && curDist == minDist) {
ret[2] = events[i].x;
}
add += events[i].e;
}
//cout << '\n';
ret[1] += val;
ret[2] += val;
//cout << u << " " << p << " " << val << " " << ret[0] << " " << ret[1] << " " << ret[2] << '\n';
return ret;
};
cout << DFS(0, -1, 0)[0] << '\n';
return 0;
}