Submission #1178372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178372		Boycl07	Tree (IOI24_tree)	C++20	18 / 100	57 ms	24208 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 par[N], num_leaf[N], leaf[N], num_wleaf[N], wei[N];
ll f[LIM], sum[LIM];

void init(int n, const vector<int> &w)
{
    for(int i = 0; i < n; ++i)
    {
        par[i] = i;
        num_leaf[i] = 1;
        leaf[i] = 1;
        num_wleaf[i] = wei[i] = w[i];
    }
}

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

void union_set(int u, int v)
{
    int pu = root(u), pv = root(v);
    num_leaf[pu] += num_leaf[pv] - leaf[u];
    num_wleaf[pu] += num_wleaf[pv] - leaf[u] * wei[u];
    leaf[u] = 0;
    par[pv] = pu;
}

ll tot_wleaf = 0;


void init(std::vector<int> P, std::vector<int> W)
{
    n = sz(P);
    init(n, W);
    for(int i = 1; i < n; ++i)
    {
        if(W[P[i]] == 1)
            union_set(P[i], i);
    }
    for(int i = 0 ; i < n; ++i) if(root(i) == i)
    {
        tot_wleaf += num_wleaf[i];
        ++f[num_leaf[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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19