Submission #1178380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178380		Boycl07	Tree (IOI24_tree)	C++20	100 / 100	102 ms	37048 KiB

tree

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

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res > val) return 0; res = val; return 1;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 2e5 + 3;
const int LOG = 20;
const int LIM = 1e6 + 3;

int n, m;

int life_lst[N], par[N], num_leaf[N], leaf[N], num_wleaf[N], wei[N];
ll f[LIM], sum[LIM];
int Maxx = 0;
ll tot_wleaf = 0;
void init(int n)
{
    for(int i = 0; i < n; ++i)
    {
        par[i] = i;
        num_leaf[i] = 1;
        leaf[i] = 1;
        life_lst[i] = Maxx - 1;
    }
}

int root(int u) {return u == par[u] ? u : par[u] = root(par[u]);}

void update(int u, int w)
{
    tot_wleaf += 1ll * num_wleaf[u] * w;
    f[num_leaf[u] - 1] += w;
}

void make_1(int u, int lst)
{
    int pu = root(u);
    update(pu, life_lst[pu] - lst);
    num_wleaf[pu] += 1;
    wei[u] = 1;
    life_lst[pu] = lst;
}

void union_set(int u, int v, int lst)
{
    int pu = root(u), pv = root(v);
    update(pu, life_lst[pu] - lst);
    update(pv, life_lst[pv] - lst);

    num_leaf[pu] += num_leaf[pv] - leaf[u];
    num_wleaf[pu] += num_wleaf[pv] - leaf[u] * wei[u];
    leaf[u] = 0;
    par[pv] = pu;
    life_lst[pu] = lst;
}

vector<int> g[N];
void init(std::vector<int> P, std::vector<int> W)
{
    n = sz(P);
    init(n);
    for(int i = 0; i < n; ++i) maximize(Maxx, W[i]);

    vector<pii> X;
    for(int i = 0; i < n; ++i)
        X.pb({W[i], i});
    for(int i = 1; i < n; ++i) g[P[i]].pb(i);
    sort(all(X));
    for(int i = n - 1; i >= 0; --i)
    {
        int u = X[i].se;
        make_1(u, W[u] - 1);
        for(int v : g[u]) union_set(u, v, W[u] - 1);
    }
    for(int i = 0; i < n; ++i)
        if(root(i) == i) update(i, life_lst[i] + 1);
    for(int i = 1e6; i >= 0; --i) f[i] += f[i + 1];
    for(int i = 1e6; i >= 0; --i) sum[i] = sum[i + 1] + f[i];

}

ll query(int L, int R)
{
    return 1ll * tot_wleaf * L + (1ll * sum[R / L] * L - 1ll * f[R / L] * (R % L));
}

• 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