Submission #1201201

#TimeUsernameProblemLanguageResultExecution timeMemory
1201201viduxTree (IOI24_tree)C++17
0 / 100
2097 ms19108 KiB
#include <bits/stdc++.h> using namespace std; //#define LOCAL #define FOR(i, n) for (int i = 0; i < n; ++i) #define REP(i, n, m) for (int i = n; i <= m; ++i) #define REPR(i, n, m) for (int i = n; i >= m; --i) #define FORR(x, a) for (auto& x : a) #define FORR2(x, y, a) for (auto& [x, y] : a) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define SZ(a) ((int)a.size()) typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; const int INF = 1e9; const ll LLINF = 1e18; vi p, w; vvi child; void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; child = vvi(SZ(p)); REP(i, 1, SZ(p)-1) { child[p[i]].push_back(i); } } long long query(int L, int R) { ll ans = 0; auto dfs = [&](int i, auto dfs) -> ll { if (SZ(child[i]) == 0) { ans += L * w[i]; return L; } ll sum = 0; FORR(j, child[i]) sum += dfs(j, dfs); if (sum > R) { ans += (sum - R) * w[i]; sum = R; } return sum; }; ll extra = dfs(0, dfs); if (extra > R) ans += extra * w[0]; return ans; } #ifdef LOCAL int main() { init({-1, 0, 0}, {1, 1, 1}); cout << query(1, 1) << endl; cout << query(1, 2) << endl; 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...