Submission #1241845

#TimeUsernameProblemLanguageResultExecution timeMemory
1241845nibertTree (IOI24_tree)C++20
0 / 100
2094 ms27448 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200005; int N; vector<int> tree[MAXN]; int weight[MAXN]; bool isLeaf[MAXN]; int leafCount[MAXN]; vector<pair<ll, ll>> segments; // a[t] * L + b[t] * R void dfs_mark_leaves_and_count(int u) { isLeaf[u] = true; leafCount[u] = 0; for (int v : tree[u]) { isLeaf[u] = false; dfs_mark_leaves_and_count(v); leafCount[u] += leafCount[v]; } if (isLeaf[u]) leafCount[u] = 1; } // Recursive decomposition void decompose(int u, ll mulA, ll mulB) { int k = leafCount[u]; if (isLeaf[u]) { segments.push_back({mulA * 1, mulB * 0}); // cost = L * W[u] return; } segments.push_back({mulA * k, mulB * (-1)}); // (kL - R) * W[u] for (int v : tree[u]) { decompose(v, mulA, mulB); } } void init(vector<int> P, vector<int> W) { N = P.size(); for (int i = 0; i < N; ++i) { tree[i].clear(); isLeaf[i] = false; } for (int i = 1; i < N; ++i) { tree[P[i]].push_back(i); } for (int i = 0; i < N; ++i) weight[i] = W[i]; dfs_mark_leaves_and_count(0); segments.clear(); decompose(0, 1, 1); // initial multipliers for L and R // Multiply weight at the segment origin for (auto& seg : segments) { seg.first *= weight[0]; seg.second *= weight[0]; } } ll query(int L, int R) { ll res = 0; for (auto& seg : segments) { res += seg.first * L + seg.second * R; } return res; }
#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...