Submission #78215

#TimeUsernameProblemLanguageResultExecution timeMemory
78215qkxwsmFireworks (APIO16_fireworks)C++14
100 / 100
315 ms142088 KiB
/* _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } }; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>; random_device(rd); mt19937 rng(rd()); template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T, class U> T nmod(T &x, U mod) { if (x >= mod) x -= mod; } template<class T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); } template<class T> T randomize(T mod) { return (uniform_int_distribution<T>(0, mod - 1))(rng); } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll #define MAXN 300013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; int N, M; int parent[MAXN]; ll dup[MAXN]; vector<int> edge[MAXN]; int subtree[MAXN], heavy[MAXN]; ll ans = 0; priority_queue<ll> pos[MAXN]; int slope[MAXN]; vector<ll> changes; void debugpq(priority_queue<ll> pq) { vector<ll> vec; while(!pq.empty()) { vec.PB(pq.top()); pq.pop(); } reverse(vec.begin(), vec.end()); for (ll x : vec) { cerr << x << ' '; } cerr << endl; } int32_t main() { ios_base::sync_with_stdio(0); // cout << fixed << setprecision(10); // cerr << fixed << setprecision(10); // freopen ("file.in", "r", stdin); // freopen ("file.out", "w", stdout); cin >> N >> M; M += N; swap(N, M); for (int i = 1; i < N; i++) { cin >> parent[i] >> dup[i]; parent[i]--; edge[parent[i]].PB(i); } for (int u = N - 1; u >= 0; u--) { subtree[u] = 1; for (int v : edge[u]) { subtree[u] += subtree[v]; } heavy[u] = N; for (int v : edge[u]) { if (subtree[v] * 2 >= subtree[u]) { heavy[u] = v; } } } // for (int i = 0; i < N; i++) // { // for (int j = 0; j < MAXN; j++) // { // dp[i][j] = LLINF; // } // if (i >= M) dp[i][0] = 0; // } // // cerr << M << " nons\n"; // for (int u = M - 1; u >= 0; u--) // { // for (int i = 0; i < MAXN; i++) // { // dp[u][i] = 0; // for (int v : edge[u]) // { // ll cost = LLINF; // for (int j = 0; j <= i; j++) // { // ckmin(cost, dp[v][j] + abs(i - (j + dup[v]))); // } // dp[u][i] += cost; // if (cost == LLINF) // { // dp[u][i] = LLINF; // break; // } // } // } // } // ans = LLINF; // for (int i = 0; i < MAXN; i++) // { // ckmin(ans, dp[0][i]); // } for (int i = M; i <= N; i++) { pos[i].push(0); pos[i].push(0); slope[i] = -1; //it's the slope BEFORE the first element! } //when slope is positive, you use all the new guys, otherwise you use the old guys for (int u = M - 1; u >= 0; u--) { // slope[u] = 0; // cerr << u << " start " << slope[u] << " has "; // debugpq(pos[u]); for (int v : edge[u]) { ll d = dup[v]; //convolve this guy with v //let L...R be the region with slope 0 //then L...L+d is slope -1 //L+d...R+d is slope 0 //R+d...INF is slope 1 //after size = 0, slope = slope[i] //after size = -slope[i], slope = 0 while(pos[v].size() > 1 - slope[v]) { pos[v].pop(); } ll R = pos[v].top(); pos[v].pop(); ll L = pos[v].top(); pos[v].pop(); // cerr << "vert " << v << ' ' << L << ' ' << R << endl; // if (pos[v].empty()) // { // pos[v].push(0); // cerr << "start " << slope[v] << endl; // } pos[v].push(L + d); pos[v].push(R + d); // cerr << v << " start " << slope[v] << " has "; // debugpq(pos[v]); slope[u] += slope[v]; } if (heavy[u] != N) { swap(pos[u], pos[heavy[u]]); } for (int v : edge[u]) { //then add this guy if (v == heavy[u]) continue; // cerr << "send from " << v << " to " << u << endl; while(!pos[v].empty()) { ll x = pos[v].top(); pos[v].pop(); // cerr << "pos " << u << " push " << x << endl; pos[u].push(x); } } // cerr << u << " start " << slope[u] << " has "; // debugpq(pos[u]); } ll curslope = slope[0], cursum = 0; while(!pos[0].empty()) { ll x = pos[0].top(); pos[0].pop(); changes.PB(x); } changes.PB(0); reverse(changes.begin(), changes.end()); for (int i = 0; i < changes.size() - 1; i++) { cursum += (changes[i + 1] - changes[i]) * curslope; ckmin(ans, cursum); curslope++; } for (int i = 1; i < N; i++) { ans += dup[i]; } cout << ans << '\n'; // cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl; return 0; }

Compilation message (stderr)

fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:256:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(pos[v].size() > 1 - slope[v])
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fireworks.cpp:305:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < changes.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...