| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1323585 | iamsazidh | Tree (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include "tree.h"
// ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
// Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) \
for (int w = 0; w < array.size(); w++) \
cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
int n;
std::vector<int> p, w;
vi cnt;
ll leaf = 0;
int dfs(vii &adj, int i, vi &W)
{
if (adj[i].size() == 0)
{
leaf++;
return 1;
}
int c = 0;
for (auto x : adj[i])
{
c += dfs(adj, x, W);
}
if (W[i] == 0)
{
cnt[c]++;
return 1;
}
else
{
return c;
}
}
void init(std::vector<int> P, std::vector<int> W)
{
n = P.size();
cnt.resize(n + 5);
vii adj(n + 1);
for (int i = 1; i < n; i++)
adj[P[i]].push_back(i);
cnt[dfs(adj, 0, W)]++;
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
}
long long query(ll L, ll R)
{
ll cost = (leaf * L) + (max(0LL, (leaf * L) - R));
if((leaf * L)<=R) return cost;
int k = R/L;
cost -= cnt[n]*(L);
cost += cnt[k]*L + (R*(cnt[n]-cnt[k]));
return cost;
}