Submission #1348838

#TimeUsernameProblemLanguageResultExecution timeMemory
1348838pandaa73Tree (IOI24_tree)C++20
0 / 100
2098 ms46388 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);

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) -> pair<int, set<pii>> {
        if(adj[v].empty()) {
            ans += (ll)L * W[v];
            return {L, {}};
        }

        int sz = 0;
        set<pii> s;
        for(auto u: adj[v]) {
            auto [sz_u, t] = dfs(u, dfs);

            sz += sz_u;

            if(t.size() > s.size()) swap(s, t);
            for(auto p: t) s.emplace(p);
        }

        while(sz > R && !s.empty() && s.begin()->fi < W[v]) {
            auto [cnt, w] = *s.begin();

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

            ans += (ll)k * w;

            s.erase(s.begin());
            if(k < cnt) s.emplace(cnt - k, w);

            sz -= k;
        }

        ans += max(0LL, (ll)(sz - R)) * W[v];

        if(sz > L) s.emplace(W[v], sz - L);

        return {sz, s};
    };

    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...