#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)
struct Node {
int num, l, r;
};
class SugoyDataStructure {
public:
vector<Node>vec; int size_ = 0; long long sum = 0;
void init() {
vec.push_back(Node{ 0,-1,-1 });
size_ = 1;
}
void add(long long pos, int x) {
int cx = 0; pos -= sum;
for (int i = 49; i >= 0; i--) {
vec[cx].num += x;
if (pos >= (1LL << i)) {
if (vec[cx].r >= 0) cx = vec[cx].r;
else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].r = size_; cx = size_; size_++; }
pos -= (1LL << i);
}
else {
if (vec[cx].l >= 0) cx = vec[cx].l;
else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].l = size_; cx = size_; size_++; }
}
}
vec[cx].num += x;
}
int getsize() {
return vec[0].num;
}
int getvalue(int p) {
int cx = 0; long long D = 0;
for (int i = 49; i >= 0; i--) {
if (vec[cx].l >= 0 && p < vec[vec[cx].l].num) cx = vec[cx].l;
else { if (vec[cx].l >= 0) { p -= vec[vec[cx].l].num; } cx = vec[cx].r; D += (1LL << i); }
}
return D + sum;
}
void AddToSum(long long x) {
sum += x;
}
};
long long N, M, A[300009], B[300009], dist[300009], rem; vector<pair<long long, long long>>G[300009];
long long P[300009]; SugoyDataStructure F[300009];
int main() {
cin >> N >> M;
for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }
for (int i = N + M; i >= 1; i--) {
if (G[i].size() == 0) {
F[i].init(); P[i] = i;
F[i].add(dist[i], 2);
}
else {
vector<pair<long long, long long>>A; long long res = 0;
for (int j = 0; j < G[i].size(); j++) {
int to = G[i][j].first, L = F[P[to]].getsize();
A.push_back(make_pair(L, P[to])); res += L;
}
sort(A.begin(), A.end(), greater<pair<long long, long long>>());
int S = A[0].second;
if (i == 1) { S = 1; F[S].init(); }
P[i] = S;
for (int j = 0; j < G[i].size(); j++) {
int to = G[i][j].first, v = P[to];
if (v == S) continue;
for (int k = 0; k < F[v].getsize(); k++) F[S].add(F[v].getvalue(k), 1);
}
for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
long long D = F[S].getsize();
long long v1 = F[S].getvalue(D - 2), v2 = F[S].getvalue(D - 1);
F[S].AddToSum(-B[i]);
F[S].add(v1 - B[i], -1); F[S].add(v1, 1);
F[S].add(v2 - B[i], -1); F[S].add(v2, 1);
}
//cout << i << ": "; for (int j = 0; j < F[P[i]].getsize(); j++) cout << F[P[i]].getvalue(j) << " "; cout << endl;
}
long long LastAnswer = rem, cx = 0;
for (int i = 0; i < F[1].getsize() - 1; i++) {
long long val = F[1].getvalue(i); cout << val << endl;
LastAnswer -= (F[1].getsize() - i - 1)*(val - cx); cx = val;
}
cout << LastAnswer << endl;
return 0;
}
Compilation message
fireworks.cpp:7:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
fireworks.cpp: In function 'int main()':
fireworks.cpp:59:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }
~~^~~~~~~~~~~~~
fireworks.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < G[i].size(); j++) {
~~^~~~~~~~~~~~~
fireworks.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < G[i].size(); j++) {
~~^~~~~~~~~~~~~
fireworks.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
~~^~~~~~~~~~~~~~~~~
fireworks.cpp:58:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
19064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
