Submission #370911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370911	2021-02-25T04:07:33 Z	azberjibiou	Designated Cities (JOI19_designated_cities)	C++17	Compilation error	0 ms	0 KB

designated_cities

#include <bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=200020;
const ll INF=1000000000000000001;
typedef struct line{
    int s, e;
    ll val;
}line;
int N, Q;
map <int, ll> v[mxN];
vector <pll> rv[mxN];
ll ans[mxN];
ll tot, rtot;
ll dep[mxN], rdep[mxN];
void dfs(int now, int pre)
{
    for(auto iter=v[now].begin();iter!=v[now].end();iter++)
    {
        if(iter->fir==pre)  continue;
        int nxt=iter->fir;
        dep[nxt]=dep[now]+iter->sec;
        tot+=iter->sec;
        dfs(nxt, now);
    }
}
void rdfs(int now, int pre)
{
    for(pll ele : rv[now])
    {
        if(ele.fir==pre)    continue;
        rdep[ele.fir]=rdep[now]+ele.sec;
        rdfs(ele.fir, now);
    }
}
void solv1()
{
    dfs(1, -1);
    rdfs(1, -1);
    for(int i=1;i<=N;i++)
    {
        ans[1]=max(ans[1], tot-dep[i]+rdep[i]);
    }
    ans[1]=rtot-ans[1];
}
typedef struct cmp1{
    bool operator()(pll a, pll b)
    {
        if(a.sec!=b.sec)    return a.sec<b.sec;
        return a.fir<b.fir;
    }
}cmp1;
set <pll, cmp1> pq;
void solv2()
{
    for(int i=1;i<=N;i++)
    {
        if(v[i].size()==2)
        {
            ll a=-1, b=-1, ia, ib, ai, bi;
            for(auto iter=v[i].begin();iter!=v[i].end();iter++)
            {
                if(a==-1)   a=iter->fir, ia=iter->sec;
                else    b=iter->fir, ib=iter->sec;
            }
            auto itera=v[a].find(i);
            ai=itera->sec;
            v[a].erase(itera);
            auto iterb=v[b].find(i);
            bi=iterb->sec;
            v[b].erase(iterb);
            v[a].insert({b, ai+ib});
            v[b].insert({a, bi+ia});
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(v[i].size()==1)
        {
            auto iter=v[i].begin();
            pq.insert({i, iter->sec});
        }
    }
    for(int i=pq.size();i<=N;i++)   ans[i]=0;
    for(int i=pq.size()-1;i>=2;i--)
    {
        pll now=*pq.begin();
        pq.erase(pq.begin());
        ans[i]=ans[i+1]+now.sec;
        auto iter=v[now.fir].begin();
        int nxt=iter->fir;
        auto itern=v[nxt].find(now.fir);
        v[nxt].erase(itern);
        if(i==2)    break;
        if(v[nxt].size()==2)
        {
            ll a=-1, b=-1, ia, ib, ai, bi;
            for(auto iter=v[nxt].begin();iter!=v[nxt].end();iter++)
            {
                if(a==-1)   a=iter->fir, ia=iter->sec;
                else        b=iter->fir, ib=iter->sec;
            }
            if(v[a].size()==1)
            {
                ll nval=v[a].begin()->sec;
                pq.erase({a, nval});
            }
            if(v[b].size()==1)
            {
                ll nval=v[b].begin()->sec;
                pq.erase({b, nval});
            }
            auto itera=v[a].find(i);
            auto iterb=v[b].find(i);
            ai=itera->sec, bi=iterb->sec;
            v[a].erase(itera);  v[b].erase(iterb);
            v[a].insert({b, ai+ib});
            v[b].insert({a, bi+ia});
            if(v[a].size()==1)  pq.insert({a, v[a].begin()->sec});
            if(v[b].size()==1)  pq.insert({b, v[b].begin()->sec});
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N-1;i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[a].insert({b, d}); v[b].insert({a, c});
        rv[a].push_back({b, c});    rv[b].push_back({a, d});
        rtot+=c;    rtot+=d;
    }
    solv1();
    solv2();
    cin >> Q;
    while(Q--)
    {
        int a;
        cin >> a;
        cout << ans[a] << '\n';
    }
}

Compilation message

In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from designated_cities.cpp:1:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = cmp1; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<long long int, long long int> >*]':
/usr/include/c++/9/bits/stl_tree.h:2095:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = cmp1; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
/usr/include/c++/9/bits/stl_tree.h:2148:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = std::pair<long long int, long long int>; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = cmp1; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
/usr/include/c++/9/bits/stl_set.h:520:48:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = cmp1; _Alloc = std::allocator<std::pair<long long int, long long int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]'
designated_cities.cpp:84:37:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~