제출 #1178380

#제출 시각아이디문제언어결과실행 시간메모리
1178380Boycl07Tree (IOI24_tree)C++20
100 / 100
102 ms37048 KiB
#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)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...