oj.uz

Submission #492252

# Submission time Handle Problem Language Result Execution time Memory
492252 2021-12-06T08:40:29 Z cuiaoxiang Fireworks (APIO16_fireworks) C++17
100 / 100
 264 ms 94404 KB 
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
  return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
// mt19937 mrand(random_device{}());
// int rnd(int x) { return mrand() % x; }
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

const int N = 3e5 + 10;
vector<ii> a[N];

template <typename T>
struct slope_trick {
  T min_f;
  priority_queue<T, vector<T>, less<>> L;
  priority_queue<T, vector<T>, greater<>> R;
  T add_l, add_r;

  void pushR(const T& x) {
    R.push(x - add_r);
  }
  T topR() const {
    if (R.empty()) return inf<T>;
    return R.top() + add_r;
  }
  T popR() {
    T ret = topR();
    if (!R.empty()) R.pop();
    return ret;
  }
  void pushL(const T& x) {
    L.push(x - add_l);
  }
  T topL() const {
    if (L.empty()) return -inf<T>;
    return L.top() + add_l;
  }
  T popL() {
    T ret = topL();
    if (!L.empty()) L.pop();
    return ret;
  }
  size_t size() { return L.size() + R.size(); }
  slope_trick() : min_f(0), add_l(0), add_r(0) {}

  // f(x) += a
  void add_all(const T& a) {
    min_f += a;
  }
  // add \_
  // f(x) += max(a - x, 0)
  void add_a_minus_x(const T& a) {
    min_f += max(T(0), a - topR());
    pushR(a);
    pushL(popR());
  }
  // add _/
  // f(x) += max(x - a, 0)
  void add_x_minus_a(const T& a) {
    min_f += max(T(0), topL() - a);
    pushL(a);
    pushR(popL());
  }
  // add \/
  // f(x) += abs(x - a)
  void add_abs(const T& a) {
    add_a_minus_x(a);
    add_x_minus_a(a);
  }
  // \/ -> \_
  // f_new(x) = min f(y) (y <= x)
  void clear_right() {
    while (!R.empty()) R.pop();
  }
  // \/ -> _/
  // f_new(x) = min f(y) (y >= x)
  void clear_left() {
    while (!L.empty()) L.pop();
  }
  // \/ -> \_/
  // f_new(x) = min f(y) (x-b <= y <= x-a)
  void expand(const T& a, const T& b) {
    assert(a <= b);
    add_l += a;
    add_r += b;
  }
  // \/. -> .\/
  // f_new(x) = f(x - a)
  void shift(const T& a) {
    expand(a, a);
  }
  // L, R will be emptied.
  T get(const T& x) {
    T ret = min_f;
    while (!L.empty()) ret += max(T(0), popL() - x);
    while (!R.empty()) ret += max(T(0), x - popR());
    return ret;
  }
  void merge(slope_trick& other) {
    if (other.size() > size()) {
      swap(other.L, L);
      swap(other.R, R);
      swap(other.add_l, add_l);
      swap(other.add_r, add_r);
      swap(other.min_f, min_f);
    }
    while (!other.R.empty()) add_x_minus_a(other.popR());
    while (!other.L.empty()) add_a_minus_x(other.popL());
    min_f += other.min_f;
  }

};

slope_trick<int64> st[N];
void dfs(int u, int parent) {
  int cnt = 0;
  for (auto& [v, w] : a[u]) {
    if (v == parent) continue;
    dfs(v, u);
    ++cnt;
    int64 topR = st[v].topR() + w;
    st[v].clear_right();
    st[v].pushR(topR);
    int64 topL = st[v].topL() + w;
    st[v].popL();
    st[v].pushL(topL);

    st[u].merge(st[v]);
  }
  if (cnt == 0) st[u].add_abs(0);
}

int main() {
  int n, m;
  cin >> n >> m;
  n += m;

  for (int i = 1; i < n; ++i) {
    int p, c;
    cin >> p >> c;
    --p;
    a[p].push_back({i, c});
  }

  dfs(0, -1);
  cout << st[0].min_f << '\n';

  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33100 KB Output is correct
2 Correct 18 ms 33100 KB Output is correct
3 Correct 15 ms 33176 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 15 ms 33140 KB Output is correct
6 Correct 16 ms 33084 KB Output is correct
7 Correct 15 ms 33196 KB Output is correct
8 Correct 17 ms 33148 KB Output is correct
9 Correct 14 ms 33196 KB Output is correct
10 Correct 15 ms 33208 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33124 KB Output is correct
2 Correct 15 ms 33100 KB Output is correct
3 Correct 14 ms 33188 KB Output is correct
4 Correct 18 ms 33096 KB Output is correct
5 Correct 15 ms 33132 KB Output is correct
6 Correct 15 ms 33132 KB Output is correct
7 Correct 16 ms 33192 KB Output is correct
8 Correct 15 ms 33100 KB Output is correct
9 Correct 14 ms 33128 KB Output is correct
10 Correct 15 ms 33188 KB Output is correct
11 Correct 15 ms 33100 KB Output is correct
12 Correct 15 ms 33100 KB Output is correct
13 Correct 16 ms 33228 KB Output is correct
14 Correct 15 ms 33228 KB Output is correct
15 Correct 15 ms 33192 KB Output is correct
16 Correct 16 ms 33120 KB Output is correct
17 Correct 15 ms 33120 KB Output is correct
18 Correct 15 ms 33100 KB Output is correct
19 Correct 15 ms 33100 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33100 KB Output is correct
2 Correct 18 ms 33100 KB Output is correct
3 Correct 15 ms 33176 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 15 ms 33140 KB Output is correct
6 Correct 16 ms 33084 KB Output is correct
7 Correct 15 ms 33196 KB Output is correct
8 Correct 17 ms 33148 KB Output is correct
9 Correct 14 ms 33196 KB Output is correct
10 Correct 15 ms 33208 KB Output is correct
11 Correct 14 ms 33124 KB Output is correct
12 Correct 15 ms 33100 KB Output is correct
13 Correct 14 ms 33188 KB Output is correct
14 Correct 18 ms 33096 KB Output is correct
15 Correct 15 ms 33132 KB Output is correct
16 Correct 15 ms 33132 KB Output is correct
17 Correct 16 ms 33192 KB Output is correct
18 Correct 15 ms 33100 KB Output is correct
19 Correct 14 ms 33128 KB Output is correct
20 Correct 15 ms 33188 KB Output is correct
21 Correct 15 ms 33100 KB Output is correct
22 Correct 15 ms 33100 KB Output is correct
23 Correct 16 ms 33228 KB Output is correct
24 Correct 15 ms 33228 KB Output is correct
25 Correct 15 ms 33192 KB Output is correct
26 Correct 16 ms 33120 KB Output is correct
27 Correct 15 ms 33120 KB Output is correct
28 Correct 15 ms 33100 KB Output is correct
29 Correct 15 ms 33100 KB Output is correct
30 Correct 15 ms 33228 KB Output is correct
31 Correct 16 ms 33292 KB Output is correct
32 Correct 16 ms 33208 KB Output is correct
33 Correct 16 ms 33352 KB Output is correct
34 Correct 16 ms 33356 KB Output is correct
35 Correct 18 ms 33456 KB Output is correct
36 Correct 17 ms 33388 KB Output is correct
37 Correct 17 ms 33480 KB Output is correct
38 Correct 18 ms 33536 KB Output is correct
39 Correct 18 ms 33508 KB Output is correct
40 Correct 17 ms 34124 KB Output is correct
41 Correct 18 ms 34152 KB Output is correct
42 Correct 18 ms 33396 KB Output is correct
43 Correct 20 ms 33816 KB Output is correct
44 Correct 19 ms 33688 KB Output is correct
45 Correct 19 ms 33748 KB Output is correct
46 Correct 19 ms 33704 KB Output is correct
47 Correct 22 ms 33716 KB Output is correct
48 Correct 19 ms 33596 KB Output is correct
49 Correct 19 ms 33716 KB Output is correct
50 Correct 19 ms 33612 KB Output is correct
51 Correct 18 ms 33584 KB Output is correct
52 Correct 19 ms 33592 KB Output is correct
53 Correct 18 ms 33748 KB Output is correct
54 Correct 18 ms 33592 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33100 KB Output is correct
2 Correct 18 ms 33100 KB Output is correct
3 Correct 15 ms 33176 KB Output is correct
4 Correct 15 ms 33196 KB Output is correct
5 Correct 15 ms 33140 KB Output is correct
6 Correct 16 ms 33084 KB Output is correct
7 Correct 15 ms 33196 KB Output is correct
8 Correct 17 ms 33148 KB Output is correct
9 Correct 14 ms 33196 KB Output is correct
10 Correct 15 ms 33208 KB Output is correct
11 Correct 14 ms 33124 KB Output is correct
12 Correct 15 ms 33100 KB Output is correct
13 Correct 14 ms 33188 KB Output is correct
14 Correct 18 ms 33096 KB Output is correct
15 Correct 15 ms 33132 KB Output is correct
16 Correct 15 ms 33132 KB Output is correct
17 Correct 16 ms 33192 KB Output is correct
18 Correct 15 ms 33100 KB Output is correct
19 Correct 14 ms 33128 KB Output is correct
20 Correct 15 ms 33188 KB Output is correct
21 Correct 15 ms 33100 KB Output is correct
22 Correct 15 ms 33100 KB Output is correct
23 Correct 16 ms 33228 KB Output is correct
24 Correct 15 ms 33228 KB Output is correct
25 Correct 15 ms 33192 KB Output is correct
26 Correct 16 ms 33120 KB Output is correct
27 Correct 15 ms 33120 KB Output is correct
28 Correct 15 ms 33100 KB Output is correct
29 Correct 15 ms 33100 KB Output is correct
30 Correct 15 ms 33228 KB Output is correct
31 Correct 16 ms 33292 KB Output is correct
32 Correct 16 ms 33208 KB Output is correct
33 Correct 16 ms 33352 KB Output is correct
34 Correct 16 ms 33356 KB Output is correct
35 Correct 18 ms 33456 KB Output is correct
36 Correct 17 ms 33388 KB Output is correct
37 Correct 17 ms 33480 KB Output is correct
38 Correct 18 ms 33536 KB Output is correct
39 Correct 18 ms 33508 KB Output is correct
40 Correct 17 ms 34124 KB Output is correct
41 Correct 18 ms 34152 KB Output is correct
42 Correct 18 ms 33396 KB Output is correct
43 Correct 20 ms 33816 KB Output is correct
44 Correct 19 ms 33688 KB Output is correct
45 Correct 19 ms 33748 KB Output is correct
46 Correct 19 ms 33704 KB Output is correct
47 Correct 22 ms 33716 KB Output is correct
48 Correct 19 ms 33596 KB Output is correct
49 Correct 19 ms 33716 KB Output is correct
50 Correct 19 ms 33612 KB Output is correct
51 Correct 18 ms 33584 KB Output is correct
52 Correct 19 ms 33592 KB Output is correct
53 Correct 18 ms 33748 KB Output is correct
54 Correct 18 ms 33592 KB Output is correct
55 Correct 22 ms 34092 KB Output is correct
56 Correct 46 ms 36876 KB Output is correct
57 Correct 79 ms 39508 KB Output is correct
58 Correct 94 ms 41200 KB Output is correct
59 Correct 120 ms 43836 KB Output is correct
60 Correct 150 ms 46488 KB Output is correct
61 Correct 176 ms 48672 KB Output is correct
62 Correct 208 ms 50068 KB Output is correct
63 Correct 232 ms 53440 KB Output is correct
64 Correct 260 ms 54360 KB Output is correct
65 Correct 132 ms 94404 KB Output is correct
66 Correct 123 ms 94320 KB Output is correct
67 Correct 115 ms 47688 KB Output is correct
68 Correct 164 ms 76628 KB Output is correct
69 Correct 194 ms 73420 KB Output is correct
70 Correct 199 ms 73120 KB Output is correct
71 Correct 255 ms 70792 KB Output is correct
72 Correct 264 ms 70808 KB Output is correct
73 Correct 230 ms 67608 KB Output is correct
74 Correct 232 ms 67784 KB Output is correct
75 Correct 242 ms 66508 KB Output is correct
76 Correct 234 ms 66532 KB Output is correct
77 Correct 251 ms 64872 KB Output is correct
78 Correct 256 ms 63804 KB Output is correct
79 Correct 194 ms 64224 KB Output is correct