Submission #1349554

#TimeUsernameProblemLanguageResultExecution timeMemory
1349554pandaa73Tree (IOI24_tree)C++20
23 / 100
2097 ms50844 KiB
#include <bits/stdc++.h>
using namespace std;

#define ff endl
#define lf "\n"
#define fi first
#define se second
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#ifdef DEBUG

constexpr bool IS_DEBUG = 1;

#define infor(fmt, ...) do { print(stderr, fmt, ##__VA_ARGS__); } while(0)
#define infof(fmt, ...) do { println(stderr, fmt, ##__VA_ARGS__); } while(0)

#else

constexpr bool IS_DEBUG = 0;

#define infor(fmt, ...)
#define infof(fmt, ...)

#endif

using ll = long long;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

template<typename... Args>
using vec = vector<Args...>;

constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;

mt19937 timmy_loves_gambling(73);

constexpr ll INF = 1e18;

int N;
vec<int> W;
vec<vec<int>> adj;

void init(vector<int> P, vector<int> W) {
    N = P.size();
    ::W = W;

    adj.resize(N);
    for(int i = 1; i < N; ++i) {
        adj[P[i]].emplace_back(i);
    }
}

long long query(int L, int R) {
    ll ans = 0;

    auto dfs = [&](int v, auto &&dfs) -> tuple<ll, ll, map<int, ll>> {
        if(adj[v].empty()) {
            ans += (ll)L * W[v];
            return {L, 0LL, {}};
        }

        ll sz = 0, sum = 0;
        map<int, ll> m;

        for(auto u: adj[v]) {
            auto [sz_u, cnt_u, m_u] = dfs(u, dfs);

            sz += sz_u;
            sum += cnt_u;

            if(m.size() < m_u.size()) swap(m, m_u);
            for(auto [k, v]: m_u) {
                m[k] += v;
            }
        }

        sum += INF;
        m[W[v]] += INF;

        while(sz > R) {
            assert(!m.empty());
            auto it = m.begin();

            auto &[w, cnt] = *it;

            ll k = min(cnt, sz - R);

            sz -= k;
            sum -= k;

            cnt -= k;
            if(cnt == 0) m.erase(it);

            ans += k * w;
        }

        while(sum > sz - L) {
            assert(!m.empty());
            auto it = prev(m.end());

            auto &[w, cnt] = *it;

            ll k = min(cnt, sum - (sz - L));

            sum -= k;

            cnt -= k;
            if(cnt == 0) m.erase(it);
        }

        return {sz, sum, m};
    };

    dfs(0, dfs);

    return ans;
}

#ifdef LOCAL
int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> P(N);
  P[0] = -1;
  for (int i = 1; i < N; i++)
    assert(1 == scanf("%d", &P[i]));
  std::vector<int> W(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &W[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; j++)
    assert(2 == scanf("%d%d", &L[j], &R[j]));
  fclose(stdin);

  init(P, W);
  std::vector<long long> A(Q);
  for (int j = 0; j < Q; j++)
    A[j] = query(L[j], R[j]);

  for (int j = 0; j < Q; j++)
    printf("%lld\n", A[j]);
  fclose(stdout);

  return 0;
}
#endif
#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...