Submission #1221768

#TimeUsernameProblemLanguageResultExecution timeMemory
1221768Theo830Tree (IOI24_tree)C++20
Compilation error
0 ms0 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; ll l,r; std::vector<int> p, w; vector<vector<int> >adj; multiset<ii>pq[60005]; ll par[60005]; ll siz[60005]; ll find_par(ll a){ if(par[a] == a){ return a; } return par[a] = find_par(par[a]); } void enose(ll a,ll b){ ll p1 = find_par(a); ll p2 = find_par(b); if(p1 == p2){ return; } if(pq[p2].size() < pq[p1].size()){ swap(p1,p2); } for(auto x:pq[p1]){ pq[p2].insert(x); } pq[p1].clear(); par[p1] = p2; siz[p2] += siz[p1]; siz[p1] = 0; } ii solve(ll idx){ if(adj[idx].empty()){ return {l,l * w[idx]}; } ii ans = {0,0}; ll sum = 0; for(auto x:adj[idx]){ ii res = solve(x); enose(idx,x); ans.S += res.S; sum += res.F; } ll p = find_par(idx); while((sum > r && !pq[p].empty()) && -(*pq[p].begin()).F < w[idx]){ auto it = pq[p].begin(); ll thelo = min((*it).S,sum - r); ll we = -(*it).F; ans.S += thelo * we; sum -= thelo; siz[p] -= thelo; ll posa = (*it).S - thelo; pq[p].erase(it); if(posa){ pq[p].insert(ii(-we,posa)); } } if(sum > r){ ans.S += w[idx] * (sum - r); sum = r; } pq[p].insert(ii(-w[idx],sum - l)); siz[p] += sum - l; while(siz[p] > sum-l){ auto it = pq[p].rbegin(); ll thelo = min((*it).S,siz[p] - (sum - l)); ll we = -(*it).F; siz[p] -= thelo; ll posa = (*it).S - thelo; pq[p].erase(it); if(posa){ pq[p].insert(ii(-we,posa)); } } ll sumi = 0; for(auto x:pq[p]){ sumi += x.S; } assert(sumi == siz[p]); ans.F = sum; return ans; } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); adj.assign(n+5,vector<int>()); f(i,1,n){ adj[p[i]].pb(i); } } long long query(int L, int R){ l = L; r = R; f(i,0,n){ pq[i].clear(); par[i] = i; siz[i] = 0; } return solve(0).S; }

Compilation message (stderr)

tree.cpp: In function 'ii solve(ll)':
tree.cpp:95:20: error: no matching function for call to 'std::multiset<std::pair<long long int, long long int> >::erase(std::reverse_iterator<std::_Rb_tree_const_iterator<std::pair<long long int, long long int> > >&)'
   95 |         pq[p].erase(it);
      |         ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/11/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:87,
                 from tree.cpp:1:
/usr/include/c++/11/bits/stl_multiset.h:639:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::erase(std::multiset<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
  639 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/11/bits/stl_multiset.h:639:28: note:   no known conversion for argument 1 from 'std::reverse_iterator<std::_Rb_tree_const_iterator<std::pair<long long int, long long int> > >' to 'std::multiset<std::pair<long long int, long long int> >::const_iterator' {aka 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator'}
  639 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/11/bits/stl_multiset.h:669:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::size_type std::multiset<_Key, _Compare, _Alloc>::erase(const key_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::size_type = long unsigned int; std::multiset<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
  669 |       erase(const key_type& __x)
      |       ^~~~~
/usr/include/c++/11/bits/stl_multiset.h:669:29: note:   no known conversion for argument 1 from 'std::reverse_iterator<std::_Rb_tree_const_iterator<std::pair<long long int, long long int> > >' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'}
  669 |       erase(const key_type& __x)
      |             ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_multiset.h:691:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::erase(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
  691 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/11/bits/stl_multiset.h:691:7: note:   candidate expects 2 arguments, 1 provided