제출 #1241847

#제출 시각아이디문제언어결과실행 시간메모리
1241847nibert트리 (IOI24_tree)C++20
0 / 100
57 ms22944 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]; ll globalA = 0, globalB = 0; // total cost = A * L + B * R void dfs_accumulate(int u) { isLeaf[u] = true; leafCount[u] = 0; for (int v : tree[u]) { isLeaf[u] = false; dfs_accumulate(v); leafCount[u] += leafCount[v]; } if (isLeaf[u]) leafCount[u] = 1; int k = leafCount[u]; if (isLeaf[u]) { globalA += 1LL * k * weight[u]; } else { // If k*L > R, then we pay (kL - R) * W[u] = k*W[u]*L - W[u]*R // So node contributes: A = k * W[u], B = -W[u] globalA += 1LL * k * weight[u]; globalB -= 1LL * weight[u]; } } 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]; globalA = 0; globalB = 0; dfs_accumulate(0); } ll query(int L, int R) { return globalA * L + globalB * R; }
#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...