Submission #1235557

#TimeUsernameProblemLanguageResultExecution timeMemory
1235557LucaIlie트리 (IOI24_tree)C++20
100 / 100
85 ms22816 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; int n; vector<int> sef; vector<long long> coefL, coefR; void endComponent(int l, int w) { coefL[l] += (long long)l * w; coefR[l] -= w; } int findSef(int v) { if (sef[v] != v) sef[v] = findSef(sef[v]); return sef[v]; } void init(vector<int> p, vector<int> w) { n = w.size(); coefL.resize(n + 1); coefR.resize(n + 1); vector<vector<int>> adj(n); for (int v = 1; v < n; v++) adj[p[v]].push_back(v); vector<pair<int, int>> order; vector<int> leaves(n), minW(n); sef.resize(n); for (int v = 0; v < n; v++) { if (adj[v].empty()) coefL[n] += w[v]; else order.push_back({w[v], v}); sef[v] = v; leaves[v] = 1; minW[v] = w[v]; } sort(order.begin(), order.end()); reverse(order.begin(), order.end()); for (auto pp: order) { int u = pp.second; int a = findSef(u); endComponent(leaves[a], minW[a] - w[u]); for (int v: adj[u]) { endComponent(leaves[v], minW[v] - w[u]); leaves[a] += leaves[v]; sef[v] = a; } minW[a] = w[u]; leaves[a]--; } endComponent(leaves[0], minW[0]); for (int i = n - 1; i >= 0; i--) { coefL[i] += coefL[i + 1]; coefR[i] += coefR[i + 1]; } } long long query(int l, int r) { int k = min(n, r / l + 1); return l * coefL[k] + r * coefR[k]; }
#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...