Submission #1213877

#TimeUsernameProblemLanguageResultExecution timeMemory
1213877adaawf트리 (IOI24_tree)C++20
100 / 100
94 ms38840 KiB
#include <bits/stdc++.h> using namespace std; long long int a[200005], d[1000005], s[200005], p[200005], da[200005], res = 0; pair<long long int, long long int> c[1000005]; vector<int> g[200005]; int Find(int x) { if (x == p[x]) return x; return p[x] = Find(p[x]); } void Merge(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; p[y] = x; s[x] += s[y]; if (da[y] == 1) da[x] = 1; } void init(vector<int> P, vector<int> w) { int n = P.size(); for (int i = 0; i < n; i++) { a[i] = w[i]; p[i] = i; s[i] = 1; if (i != 0) { g[P[i]].push_back(i); } } vector<pair<int, int>> b; for (int i = 0; i < n; i++) { if (g[i].empty()) res += w[i]; else b.push_back({w[i], i}); } sort(b.begin(), b.end()); for (int i = (int)b.size() - 1; i >= 0; i--) { int h = b[i].second; if (da[Find(h)] == 1) { d[s[Find(h)]] -= b[i].first; } s[Find(h)]--; for (int w : g[h]) { if (da[Find(w)] == 1) { d[s[Find(w)]] -= b[i].first; } Merge(h, w); } da[Find(h)] = 1; d[s[Find(h)]] += b[i].first; } for (int i = 1000001; i >= 1; i--) { c[i] = c[i + 1]; c[i].first += d[i] * i; c[i].second += d[i]; } } long long int query(int l, int r) { int h = r / l + 1; return res * l + c[h].first * l - c[h].second * r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...