Submission #229388

#	Time	Username	Problem	Language	Result	Execution time	Memory
229388		Ruxandra985	Magic Tree (CEOI19_magictree)	C++14	100 / 100	187 ms	36984 KiB

magictree

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
map <int , long long> dp[DIMN] , aux;
vector <int> v[DIMN];
pair <int,int> fruits[DIMN];

int under[DIMN];

map <int , long long> :: iterator it , it2;

map <int , long long> :: reverse_iterator itt;


void dfs (int nod){
    int vecin , mom , i;
    long long val , win;

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        dfs (vecin);

        if (dp[nod].size() < dp[vecin].size()){
            swap(dp[nod] , dp[vecin]);
        }
        /// dp[nod] e mereu mai mare ca sa parcurg mereu ceva cat mai mic


        for (it = dp[vecin].begin() ; it != dp[vecin].end() ; it++){

            mom = it->first;
            val = it->second;

            dp[nod][mom] += val;

        }

    }


    /// momentan dp[nod] e un fel de vector de frecventa

    if (fruits[nod].first){

        /// nod are un fruct, vreau sa vad daca e worth it sa il bag

        dp[nod][fruits[nod].first] += fruits[nod].second;

        /// daca as lua fructul , nu as mai putea sa iau nimic mai mare din fii

        win = fruits[nod].second;

        while (win > 0){

            it = dp[nod].upper_bound(fruits[nod].first);

            if (it == dp[nod].end())
                break;

            mom = it->first;
            val = it->second;

            /// mom > it
            /// daca aleg sa iau fructul, e clar ca va trebui sa renunt la it

            win = win - val;

            if (win > 0){ /// am renuntat si oricum castig ceva

                dp[nod].erase(it);

            }
            else { /// nu mai am niciun avantaj in mom asta

                it->second = -win;

            }

        }



    }


}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , tt , nod , mom , val;
    long long sol;
    fscanf (fin,"%d%d%d",&n,&m,&k);
    for (i = 2 ; i <= n ; i++){
        fscanf (fin,"%d",&tt);
        v[tt].push_back(i);
    }
    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d%d",&nod,&mom,&val);
        fruits[nod] = make_pair(mom , val);
    }


    dfs(1);


    sol = 0;

    for (it = dp[1].begin() ; it != dp[1].end() ; it++){
        sol += it->second;
    }

    fprintf (fout,"%lld" , sol);

    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:95:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:97:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&tt);
         ~~~~~~~^~~~~~~~~~~~~~
magictree.cpp:101:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&nod,&mom,&val);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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