Submission #1217507

#TimeUsernameProblemLanguageResultExecution timeMemory
1217507dostsTree (IOI24_tree)C++20
0 / 100
2098 ms42308 KiB
#include "tree.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9,N = 2e5+1; int n; vector<int> p, w; vi edges[N]; pii dp[N]; int L,R; void dfs(int node){ dp[node] = {0,0}; for (auto it : edges[node]) { dfs(it); dp[node].ff+=dp[it].ff; dp[node].ss+=dp[it].ss; } if (dp[node].ss > R) { dp[node].ff+=w[node]*abs(dp[node].ss-R); dp[node].ss = R; }else if (dp[node].ss < L) dp[node].ff+=w[node]*abs(L-dp[node].ss),dp[node].ss = L; cerr << node sp dp[node].ff sp dp[node].ss << '\n'; } void init(vector<signed> P, vector<signed> W) { p = vi(all(P)); w = vi(all(W)); n = (int)p.size(); for (int i=1;i<n;i++) { edges[p[i]].push_back(i); } } long long query(signed l, signed r) { L = l,R = r; dfs(0); return dp[0].ff; }
#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...