제출 #1237134

#제출 시각아이디문제언어결과실행 시간메모리
1237134LucaIlieTree (IOI24_tree)C++20
100 / 100
88 ms22452 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5; int n; int sef[MAX_N], leaves[MAX_N], minW[MAX_N]; long long coefL[MAX_N + 1], coefR[MAX_N + 1]; vector<int> adj[MAX_N]; void endComp(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 = p.size(); for (int v = 1; v < n; v++) adj[p[v]].push_back(v); vector<pair<int, int>> ord; for (int v = 0; v < n; v++) { if (adj[v].empty()) coefL[n] += w[v]; else ord.push_back({w[v], v}); sef[v] = v; leaves[v] = 1; minW[v] = w[v]; } sort(ord.begin(), ord.end()); reverse(ord.begin(), ord.end()); for (auto pp: ord) { int u = pp.second; int a = findSef(u); endComp(leaves[a], minW[a] - w[u]); for (int v: adj[u]) { endComp(leaves[v], minW[v] - w[u]); leaves[a] += leaves[v]; sef[v] = a; } minW[a] = w[u]; leaves[a]--; } endComp(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...