Submission #1225556

#TimeUsernameProblemLanguageResultExecution timeMemory
1225556TrumlingTree (IOI24_tree)C++20
7 / 100
69 ms30868 KiB
//Trumling © //Αφόδευε υψηλά και ηγνάντει #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define F first #define S second #define enter cout<<'\n'; #define INF 99999999999999 #define MOD 1000000007 #define all(x) x.begin(),x.end() #include "tree.h" int n; vector<ll> w; vector<vector<ll>>g; vector<ll>times; vector<ll>v; vector<ll>pre; void dfs(int start,int pre) { for(auto x:g[start]) if(x!=pre) { dfs(x,start); if(w[start]==0) { v.pb(times[x]); times[start]=1; } else times[start]+=times[x]; } if(g[start].size()==1 && start!=pre) times[start]=1; } void init(std::vector<int> p, std::vector<int> W) { for(auto x:W) w.pb(x); n = (int)p.size(); g.assign(n,vector<ll>()); times.assign(n,0); for(int i=1;i<n;i++) { // cout<<i<<' '<<p[i]<<','; g[i].pb(p[i]); g[p[i]].pb(i); } dfs(0,0); v.pb(times[0]); sort(all(v)); for(auto x:v) { if(pre.size()==0) pre.pb(x); else pre.pb(pre.back() + x); } } long long query(int L, int R) { ll sz=pre.size(); ll pos=upper_bound(all(v),R/L)-v.begin(); ll l=((pos==0)?0:pre[pos-1]*L); ll r=2*(pre[sz-1] - ((pos==0)?0:pre[pos-1]))*L; return l + ((r==0)?0:r - R); }
#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...