Submission #1242486

#TimeUsernameProblemLanguageResultExecution timeMemory
1242486mychecksedadTree (IOI24_tree)C++20
10 / 100
2094 ms24300 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define vi vector<int> #define pb push_back #define pii pair<int,int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define ll long long int const int N = 2e5+100; int n; std::vector<int> p, w; vi g[N]; ll dp[N], sum[N]; ll L, R; void dfs(int v){ sum[v] = 0; dp[v] = 0; for(int u: g[v]){ dfs(u); dp[v] += dp[u]; sum[v] += sum[u]; } if(sum[v] < L){ dp[v] += (L-sum[v]) * w[v]; sum[v] = L; }else if(sum[v] <= R){ // nothing }else{ dp[v] += abs(R-sum[v])*w[v]; sum[v] = R; } } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); for(int i = 1; i < n; ++i) g[P[i]].pb(i); } long long query(int l, int r) { L = l, R = r; dfs(0); return dp[0]; }
#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...