| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1213871 | adaawf | Tree (IOI24_tree) | C++20 | 0 ms | 0 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);
}
d[s[Find(h)]] += b[i].first;
da[Find(h)] = 1;
}
for (int i = 1000000; 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;
return res * l + c[h].first * l - c[h].second * r;
}
int main() {
init({-1, 0, 0}, {1, 1, 1});
cout << query(1, 1) << '\n';
cout << query(1, 2) << '\n';
}