Submission #1221777

#TimeUsernameProblemLanguageResultExecution timeMemory
1221777Theo830Tree (IOI24_tree)C++20
18 / 100
62 ms22432 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training #include "tree.h" int n; long long leaf; std::vector<int> p, w; vector<vector<int> >adj; vector<ll>ex; ll pre[200005]; ll solve(ll idx,bool b){ ll sum = w[idx] ^ 1; if(adj[idx].empty()){ sum = 1; } if(w[idx] == 0){ for(auto x:adj[idx]){ solve(x,1); } } else{ for(auto x:adj[idx]){ sum += solve(x,0); } } b &= w[idx]; if(b){ ex.pb(sum); } return sum; } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; leaf = 0; ex.clear(); n = (int)p.size(); adj.assign(n+5,vector<int>()); f(i,1,n){ adj[p[i]].pb(i); } f(i,0,n){ if(adj[i].size() == 0 && w[i]){ leaf++; } } solve(0,1); sort(all(ex)); pre[0] = 0; f(i,0,ex.size()){ pre[i+1] = pre[i] + ex[i]; } } long long query(int L, int R){ ll ans = leaf * L; ll l = 0,r = ex.size()-1; ll pos = ex.size(); while(l <= r){ ll mid = (l+r)/2; if(ex[mid] * L > R){ r = mid - 1; pos = min(pos,mid); } else{ l = mid + 1; } } ans -= (ex.size() - pos) * R; ans += (pre[ex.size()] - pre[pos]) * L; return ans; }
#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...