Submission #74392

#	Time	Username	Problem	Language	Result	Execution time	Memory
74392		rKrPaN	Paprike (COI18_paprike)	C++98	100 / 100	196 ms	50608 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,k;
long long ljut[100010];
vector <long long int> v[1000010];
long long broj = 0;

///      DFS

int dfs(int x, int par){

    vector <long long> vec;
    long long summ= 0;
    if (par != -1 && (int)v[x].size() == 1){
        return ljut[x];
    }
    for (int i = 0; i < (int)v[x].size(); i++){
        if (v[x][i] != par){
            vec.push_back(dfs(v[x][i],x));
            summ+= vec[(int)vec.size()-1];
        }
    }

    sort(vec.begin(),vec.end());
    summ+= ljut[x];
    while(summ > k){
    	summ -= vec[(int)vec.size()-1];
		vec.pop_back();
		broj++;

	}

    return summ;
}

///     MAIN

int main (){


    cin >> n >> k;

    for (int i = 1; i <= n; i++){
        cin >> ljut[i];
    }

    for (int j = 2; j <= n; j++){
        long long a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    long long var = dfs(1,-1);

	cout << broj << "\n";


    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:58:15: warning: unused variable 'var' [-Wunused-variable]
     long long var = dfs(1,-1);
               ^~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49