#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int N, M;
vvii edges;
int edgesn;
vi srt[6000000];
void merge(vi &dst, vi &s1, vi &s2) {
dst.resize(s1.size()+s2.size());
int pdst = 0, ps1 = 0, ps2 = 0;
while (true) {
if (ps1 == s1.size() && ps2 == s2.size()) return;
if (ps1 == s1.size()) {
dst[pdst++] = s2[ps2++];
}
else if (ps2 == s2.size()) {
dst[pdst++] = s1[ps1++];
}
else {
if (s1[ps1] < s2[ps2]) {
dst[pdst++] = s1[ps1++];
}
else {
dst[pdst++] = s2[ps2++];
}
}
}
}
void dfs(int x, int d) {
if (edges[x].size() > 0) {
for (int i = 0; i < edges[x].size(); i++) {
dfs(edges[x][i].first, d + edges[x][i].second);
}
if (edges[x].size() == 1) {
srt[x] = srt[edges[x][0].first];
}
else {
merge(srt[x], srt[edges[x][0].first], srt[edges[x][1].first]);
}
}
else {
srt[x].resize(1);
srt[x][0] = d;
}
}
void predfs(int x) {
if (edges[x].size() > 2) {
for (int i = 0; i < edges[x].size()/2; i++) {
edges[edgesn].pb(edges[x][i]);
}
for (int i = edges[x].size()/2; i < edges[x].size(); i++) {
edges[edgesn+1].pb(edges[x][i]);
}
edges[x].clear();
edges[x].pb(mp(edgesn, 0));
edges[x].pb(mp(edgesn+1, 0));
edgesn += 2;
}
for (int i = 0; i < edges[x].size(); i++) {
predfs(edges[x][i].first);
}
}
void dbgdfs(int x, int b) {
for (int i = 0; i < b; i++) cerr << "\t";
cerr << x << ": ";
for (int i = 0; i < srt[x].size(); i++) cerr << srt[x][i] << " ";
cerr << endl;
for (int i = 0; i < edges[x].size(); i++) {
dbgdfs(edges[x][i].first, b+1);
}
}
ll func(int x, int t, int inlen) {
ll sum = 0;
int sz = srt[x].size();
int lmid = srt[x][(sz-1)/2], umid = srt[x][sz/2];
if (lmid > t) {
int tgtdec = lmid - t;
tgtdec = min(tgtdec, inlen);
sum += tgtdec;
for (int i = 0; i < edges[x].size(); i++) {
sum += func(edges[x][i].first, t + tgtdec, edges[x][i].second);
}
}
else if (umid < t) {
int tgtinc = t - umid;
sum += tgtinc;
for (int i = 0; i < edges[x].size(); i++) {
sum += func(edges[x][i].first, t - tgtinc, edges[x][i].second);
}
}
else {
for (int i = 0; i < edges[x].size(); i++) {
sum += func(edges[x][i].first, t, edges[x][i].second);
}
}
return sum;
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
scanf("%d%d", &N, &M);
edges.resize(20*(N+M));
edgesn = N+M+1;
for (int i = 2; i <= N; i++) {
int a, b; scanf("%d%d", &a, &b);
edges[a].pb(mp(i, b));
}
for (int i = N+1; i <= N+M; i++) {
int a, b; scanf("%d%d", &a, &b);
edges[a].pb(mp(i, b));
}
predfs(1);
dfs(1, 0);
//dbgdfs(1, 0);
int l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
while (r > l+3) {
int mid = (l+r)/2;
ll cost1 = func(1, mid, 0);
ll cost2 = func(1, mid+1, 0);
if (cost2 < cost1) {
l = mid+1;
}
else {
r = mid+1;
}
}
ll best = (ll)1e18;
for (int i = l; i < r; i++) {
//cerr << i << endl;
ll cost = func(1, i, 0);
//cerr << cost << endl;
best = min(best, cost);
}
printf("%lld\n", best);
return 0;
}
Compilation message
fireworks.cpp: In function 'void merge(vi&, vi&, vi&)':
fireworks.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size() && ps2 == s2.size()) return;
^
fireworks.cpp:23:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size() && ps2 == s2.size()) return;
^
fireworks.cpp:24:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size()) {
^
fireworks.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (ps2 == s2.size()) {
^
fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp: In function 'void predfs(int)':
fireworks.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size()/2; i++) {
^
fireworks.cpp:64:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = edges[x].size()/2; i < edges[x].size(); i++) {
^
fireworks.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp: In function 'void dbgdfs(int, int)':
fireworks.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < srt[x].size(); i++) cerr << srt[x][i] << " ";
^
fireworks.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp: In function 'll func(int, int, int)':
fireworks.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp: In function 'int main(int, char**)':
fireworks.cpp:119:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
fireworks.cpp:123:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^
fireworks.cpp:127:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
142648 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
142648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
142648 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
142648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
142648 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
142648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
142648 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
142648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
