Submission #1213877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213877		adaawf	Tree (IOI24_tree)	C++20	100 / 100	94 ms	38840 KiB

tree

#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;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19