Submission #1191789

#TimeUsernameProblemLanguageResultExecution timeMemory
1191789hamzabcTree (IOI24_tree)C++20
Compilation error
0 ms0 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define sp << " " << int N; vector<int> parent; vector<vector<int>> childs; vector<long long> weights; vector<int> leafsize; vector<array<long long, 3>> searchspace; vector<int> eulerstart, eulerend; int timer = -1; class Mintre{ private: vector<array<long long, 2>> tre; vector<long long> lazy; int size; void _update(int ind, int a, int b, int l, int r, int s){ a -= lazy[s]; if (r < ind || l > ind) return; if (l == r){ tre[s][0] = a; tre[s][1] = b; return; } int m = (l + r) >> 1; _update(ind, a, b, l, m, s << 1); _update(ind, a, b, m + 1, r, (s << 1) | 1); tre[s] = min(tre[s << 1], tre[(s << 1) | 1]); tre[s][0] += lazy[s]; } void _add(int tl, int tr, int a, int l, int r, int s){ if (r < tl || l > tr) return; if (tl <= l && r <= tr){ lazy[s] = a; tre[s] = min(tre[s << 1], tre[(s << 1) | 1]); tre[s][0] += lazy[s]; return; } int m = (l + r) >> 1; _add(tl, tr, a, l, m, s << 1); _add(tl, tr, a, m + 1, r, (s << 1) | 1); tre[s] = min(tre[s << 1], tre[(s << 1) | 1]); tre[s][0] += lazy[s]; } array<long long, 2> _query(int tl, int tr, int l, int r, int s){ if (r < tl || l > tr) return { 1e18, -1 }; if (tl <= l && r <= tr){ return tre[s]; } int m = (l + r) >> 1; auto f = min(_query(tl, tr, l, m, s << 1), _query(tl, tr, m + 1, r, (s << 1) | 1)); f[0] += lazy[s]; return f; } public: void init(int sz){ size = sz; tre.resize(sz * 4); lazy.resize(sz * 4); } void update(int x, int a, int b){ _update(x, a, b, 0, size, 1); } void add(int l, int r, int a){ _add(l, r, a, 0, size, 1); } array<long long, 2> query(int l, int r){ return _query(l, r, 0, size, 1); } }; class Addtre{ private: vector<int> tre; int size; void _update(int ind, int a, int l, int r, int s){ if (r < ind || l > ind) return; if (l == r){ tre[s] += a; return; } int m = (l + r) >> 1; _update(ind, a, l, m, s << 1); _update(ind, a, m + 1, r, (s << 1) | 1); tre[s] = tre[s << 1] + tre[(s << 1) | 1]; } int _query(int tl, int tr, int l, int r, int s){ if (r < tl || l > tr) return 0; if (tl <= l && r <= tr){ return tre[s]; } int m = (l + r) >> 1; return _query(tl, tr, l, m, s << 1) + _query(tl, tr, m + 1, r, (s << 1) | 1); } public: void init(int sz){ size = sz; tre.resize(sz * 4); } void update(int x, int a){ _update(x, a, 0, size, 1); } int query(int l, int r){ return _query(l, r, 0, size, 1); } }; Addtre Sleafs; Mintre Sweights; void dfs(int a){ timer++; eulerstart[a] = timer; Sweights.update(eulerstart[a], weights[a], a); if (!childs[a].size()){ eulerend[a] = timer; Sleafs.update(eulerstart[a], 1); return; } leafsize[a] = 0; for (auto u : childs[a]){ dfs(u); leafsize[a] += leafsize[u]; } eulerend[a] = timer; } void solve(int a, int d){ Sweights.update(eulerstart[a], 1e18, -1); if (childs[a].size() == 0){ searchspace[N - 1][0] += 1; return; } if (a == 0){ while (Sweights.query(eulerstart[a] + 1, eulerend[a])[0] < 1e9){ solve(Sweights.query(eulerstart[a] + 1, eulerend[a])[1], Sleafs.query(eulerstart[a], eulerend[a])); } int l = Sleafs.query(eulerstart[a], eulerend[a]); searchspace[l][0] += l * weights[a]; searchspace[l][1] -= weights[a]; }else{ int l = Sleafs.query(eulerstart[a], eulerend[a]); Sleafs.update(eulerstart[a], -l + 1); Sweights.add(eulerstart[a] + 1, eulerend[a], -weights[a]); searchspace[d][0] += d * weights[a]; searchspace[d][1] += -weights[a]; searchspace[l - 1][0] -= d * weights[a]; searchspace[l - 1][1] -= -weights[a]; searchspace[l - 1][0] += (l - 1) * weights[a]; } while (Sweights.query(eulerstart[a] + 1, eulerend[a])[0] < 1e9){ solve(Sweights.query(eulerstart[a] + 1, eulerend[a])[1], Sleafs.query(eulerstart[a], eulerend[a])); } } void init(vector<int> P, vector<int> W) { N = P.size(); parent.resize(N); childs.resize(N); weights.resize(N); leafsize.resize(N); searchspace.resize(N + 1); Sleafs.init(N); Sweights.init(N); eulerstart.resize(N); eulerend.resize(N); for (int i = 0; i < N; i++){ weights[i] = W[i]; parent[i] = P[i]; if (i) childs[P[i]].push_back(i); } dfs(0); solve(0, 0); for (int i = N - 1; i >= 0; i--){ searchspace[i][0] += searchspace[i + 1][0]; searchspace[i][1] += searchspace[i + 1][1]; searchspace[i][2] += searchspace[i + 1][2]; } } long long query(int L, int R) { return searchspace[R / L][0] * L + searchspace[R / L][1] * R + searchspace[R / L][2]; }

Compilation message (stderr)

tree.cpp: In member function 'std::array<long long int, 2> Mintre::_query(int, int, int, int, int)':
tree.cpp:57:25: error: narrowing conversion of '1.0e+18' from 'double' to 'long long int' [-Wnarrowing]
   57 |       return { 1e18, -1 };
      |                         ^
tree.cpp: In function 'void solve(int, int)':
tree.cpp:145:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  145 |   Sweights.update(eulerstart[a], 1e18, -1);
      |                                  ^~~~