Submission #1202587

#TimeUsernameProblemLanguageResultExecution timeMemory
1202587midiTree (IOI24_tree)C++20
0 / 100
65 ms8260 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define vc vector typedef vc<ll> vcll; typedef vc<bool> vcb; #define pr pair typedef pr<ll, ll> prll; typedef set<ll> setll; typedef map<ll,ll> mapll; #define uset unordered_set typedef uset<ll> usetll; #define umap unordered_map typedef umap<ll,ll> umapll; #define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++) #define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--) #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define mp make_pair #define fi first #define se second #define sz size #define all(x) (x).begin(), (x).end() #define all0(x, n) (x).begin(), (x).begin()+n #define all1(x, n) (x).begin()+1, (x).begin()+n+1 #define allrev(x) (x).rbegin(), (x).rend() #define in(v, s) ((s).find((v)) != (s).end()) #define GCD(x, y) __gcd(abs((x)), abs((y))) #define INF (LLONG_MAX>>3ll) #define MOD (1'000'000'007ll) #define mxN (100'010ll) inline void maxa(ll &a, ll b) { if (a<b) a=b; } inline void mina(ll &a, ll b) { if (a>b) a=b; } inline void print (vcll &a, ll n=-1, string name="") { cout << name << ": "; if (n==-1) for (ll x:a) printf("%lli ", x); else { ll i; f0r(i,1,n) printf("%lli ", a[i]); } printf("\n"); } ll n, L, R; vcll par(mxN), w(mxN); vc<vcll> gr(mxN); void init (vc<int> P, vc<int> W) { ll u; n=P.sz(); f0r(u,1,n) par[u]=P[u-1]+1; par[1]=0; f0r(u,1,n) w[u]=W[u-1]; f0r(u,1,n) gr[par[u]].pb(u); } prll dfs1 (ll u=1) // {sum, cost} { if (gr[u].empty()) return {L, L*w[u]}; ll s=0, c=0; for (ll v:gr[u]) { prll res=dfs1(v); s+=res.fi; c+=res.se; } if (s>R) { c += (s-R)*w[u]; s=R; } return {s,c}; } inline ll subtask1() { return dfs1().se; } ll query (int l, int r) { L=l, R=r; return subtask1(); } inline void pqry (ll l, ll r) { printf("query(%lli, %lli): %lli\n", l, r, query(l,r)); } /* int main() { // cin.tie(0); cout.tie(0); // ios_base::sync_with_stdio(0); srand(time(0)); freopen("file.in", "r", stdin); init({-1, 0, 0}, {1, 1, 1}); pqry(1,1); pqry(1,2); return 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...