#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef vector<ll> vll;
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;
vll srt[6000000];
void merge(vll &dst, vll &s1, vll &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, ll 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, ll t, ll inlen) {
ll sum = 0;
int sz = srt[x].size();
ll lmid = srt[x][(sz-1)/2], umid = srt[x][sz/2];
if (lmid > t) {
ll tgtdec = lmid - t;
tgtdec = min(tgtdec, inlen);
sum += tgtdec;
if (lmid - t > inlen) return 1e18;
for (int i = 0; i < edges[x].size(); i++) {
if (sum >= 1e18) return 1e18;
sum += func(edges[x][i].first, t + tgtdec, edges[x][i].second);
}
}
else if (umid < t) {
ll tgtinc = t - umid;
if (inlen == 0) tgtinc = 0;
sum += tgtinc;
for (int i = 0; i < edges[x].size(); i++) {
if (sum >= 1e18) return 1e18;
sum += func(edges[x][i].first, t - tgtinc, edges[x][i].second);
}
}
else {
for (int i = 0; i < edges[x].size(); i++) {
if (sum >= 1e18) return 1e18;
sum += func(edges[x][i].first, t, edges[x][i].second);
}
}
if (sum >= 1e18) return 1e18;
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);
ll l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
while (r > l+3) {
ll mid = (l+r)/2;
ll cost1 = func(1, mid, 0);
ll c2p = mid+1;
ll cost2 = func(1, c2p, 0);
while (cost2 == cost1) {
c2p++;
cost2 = func(1, c2p, 0);
}
if (cost2 < cost1) {
l = mid+1;
}
else {
r = mid+1;
}
}
ll best = (ll)1e18;
l = srt[1][0], r = srt[1][srt[1].size()-1]+1;
for (ll 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(vll&, vll&, vll&)':
fireworks.cpp:24:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size() && ps2 == s2.size()) return;
^
fireworks.cpp:24:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size() && ps2 == s2.size()) return;
^
fireworks.cpp:25:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps1 == s1.size()) {
^
fireworks.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (ps2 == s2.size()) {
^
fireworks.cpp: In function 'void dfs(int, ll)':
fireworks.cpp:44: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:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size()/2; i++) {
^
fireworks.cpp:65: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:73: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:81: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:83: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, ll, ll)':
fireworks.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
fireworks.cpp:112: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:126: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:130: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:134: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 |
36 ms |
142648 KB |
Output is correct |
| 2 |
Execution timed out |
2000 ms |
142648 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
142648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
142648 KB |
Output is correct |
| 2 |
Execution timed out |
2000 ms |
142648 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
142648 KB |
Output is correct |
| 2 |
Execution timed out |
2000 ms |
142648 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
