Submission #1248584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248584		qwerasdfzxcl	Tree (IOI24_tree)	C++20	70 / 100	145 ms	49504 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int SZ = 1001000;

int n;
vector<int> adj[200200], buf[SZ];
ll a[200200], sum;

struct Seg{
    ll tree[SZ*2];
    int sz;

    void init(int n){sz = n;}
    void update(ll p, ll x){
        if (p >= sz) return;
        for (p+=sz;p;p>>=1) tree[p] += x;
    }
    ll query(int l, int r){
        ++r;
        ll ret = 0;
        for (l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if (l&1) ret += tree[l++];
            if (r&1) ret += tree[--r];
        }
        return ret;
    }
}tree1, tree2;

struct DSU{
    int path[200200], rt[200200];
    ll sum[200200];

    void init(int n){
        for (int i=1;i<=n;i++) path[i] = i;
    }

    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }

    void toggle(int x, int t, ll v){
        assert(!rt[x]);
        rt[x] = t;
        sum[x] = v;
    }

    void push(int x, int t){
        x = find(x);
        tree1.update(sum[x], sum[x] * (rt[x] - t));
        tree2.update(sum[x], rt[x] - t);
        rt[x] = t;
    }

    void merge(int x, int y, int t){
        x = find(x);
        y = find(y);
        if (!rt[x] || !rt[y]) return;

        push(x, t);
        push(y, t);

        if (x==y) return;

        path[x] = y;
        sum[y] += sum[x];
    }
}dsu;

void init(std::vector<int> P, std::vector<int> W) {
    n = P.size();
    for (int i=1;i<n;i++) adj[P[i]+1].push_back(i+1);
    for (int i=0;i<n;i++) a[i+1] = W[i];

    for (int i=1;i<=n;i++) if (adj[i].empty()) sum += a[i];

    dsu.init(n);
    tree1.init(SZ);
    tree2.init(SZ);

    for (int i=1;i<=n;i++) if (!adj[i].empty()) buf[a[i]].push_back(i);

    for (int t=SZ-1;t>=1;t--){
        for (auto &x:buf[t]){
            dsu.toggle(x, t, max((int)adj[x].size() - 1, 0));
            dsu.merge(x, P[x-1]+1, t);
            for (auto &y:adj[x]) dsu.merge(x, y, t);
        }
    }

    dsu.push(1, 0);
}

long long query(int L, int R) {
    return sum * L + tree1.query((R-L) / L + 1, SZ-1) * L - tree2.query((R-L) / L + 1, SZ-1) * (R-L);
}

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