Submission #1183440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183440		filipsumic	Magic Tree (CEOI19_magictree)	C++20	100 / 100	173 ms	39456 KiB

magictree

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pi pair<ll, ll>
#define all(x) x.begin(), x.end()

using namespace std;



void DFS(int cvor, int& n, vector<vector<int>>& graf, vector<pi>& voce, vector<multiset<pi>>& promene)
{
    if(graf[cvor].size()==0)
    {
        if(voce[cvor].first!=0 && voce[cvor].second!=0)
            promene[cvor].insert({voce[cvor].first, voce[cvor].second});
        return;
    }
    for(auto u:graf[cvor]) DFS(u, n, graf, voce, promene);
    int tren=graf[cvor][0];
    for(int i=1; i<graf[cvor].size(); i++)
    {
        if(promene[graf[cvor][i]].size()>promene[tren].size())
        {
            for(auto u: promene[tren])
            {
                promene[graf[cvor][i]].insert(u);
            }
            move(promene[tren]);
            tren=graf[cvor][i];
        }
        else
        {
            for(auto u: promene[graf[cvor][i]]) promene[tren].insert(u);
            move(promene[graf[cvor][i]]);
        }
    }
    promene[cvor]=move(promene[tren]);
    if(voce[cvor].first==0 && voce[cvor].second==0) return;
    else
    {
        ll d=voce[cvor].first;
        ll x=voce[cvor].second;
        promene[cvor].insert({d, x});
        auto it=promene[cvor].upper_bound({d, LLONG_MAX});
        /*if(cvor==5)
            {
                cout<<d<<" "<<x<<"\n";
                cout<<(*it).first<<" "<<(*it).second<<"\n";
            }*/
        ll sum=(*it).second;
        while(it!=promene[cvor].end() && sum<=x)
        {
            auto brisi=it;
            ++it;
            /*if(cvor==5)
            {
                cout<<(*brisi).first<<" "<<(*brisi).second<<"\n";
                cout<<(*it).first<<" "<<(*it).second<<"\n";
            }*/
            promene[cvor].erase(brisi);
            sum+=(*it).second;
        }
        //if(cvor==5) cout<<"skibi\n";
        if(it!=promene[cvor].end())
        {
            ll dv=(*it).first;
            ll pv=(*it).second;
            promene[cvor].insert({dv, sum-pv-x});
        }
    }

}


int main()
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(0);*/

    int n, m, k;
    cin>>n>>m>>k;
    vector<vector<int>> graf(n+5);
    for(int i=2; i<=n; i++)
    {
        int p;
        cin>>p;
        graf[p].pb(i);
    }
    vector<pi> voce(n+5);
    for(int i=1; i<n+1; i++) {voce[i]={0, 0};}
    for(int i=0; i<m; i++)
    {
        ll vj, dj, wj;
        cin>>vj>>dj>>wj;
        voce[vj]={dj, wj};
    }
    vector<multiset<pi>> promene(n+5);
    DFS(1, n, graf, voce, promene);
    ll rez=0;
    for(auto u:promene[1]) rez+=u.second;
    cout<<rez;
}

Compilation message (stderr)

magictree.cpp: In function 'void DFS(int, int&, std::vector<std::vector<int> >&, std::vector<std::pair<long long int, long long int> >&, std::vector<std::multiset<std::pair<long long int, long long int> > >&)':
magictree.cpp:29:17: warning: ignoring return value of 'constexpr typename std::remove_reference<_Tp>::type&& std::move(_Tp&&) [with _Tp = std::multiset<std::pair<long long int, long long int> >&; typename std::remove_reference<_Tp>::type = std::multiset<std::pair<long long int, long long int> >]', declared with attribute 'nodiscard' [-Wunused-result]
   29 |             move(promene[tren]);
      |             ~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from magictree.cpp:1:
/usr/include/c++/11/bits/move.h:104:5: note: declared here
  104 |     move(_Tp&& __t) noexcept
      |     ^~~~
magictree.cpp:35:17: warning: ignoring return value of 'constexpr typename std::remove_reference<_Tp>::type&& std::move(_Tp&&) [with _Tp = std::multiset<std::pair<long long int, long long int> >&; typename std::remove_reference<_Tp>::type = std::multiset<std::pair<long long int, long long int> >]', declared with attribute 'nodiscard' [-Wunused-result]
   35 |             move(promene[graf[cvor][i]]);
      |             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from magictree.cpp:1:
/usr/include/c++/11/bits/move.h:104:5: note: declared here
  104 |     move(_Tp&& __t) noexcept
      |     ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17