Submission #78955

#	Time	Username	Problem	Language	Result	Execution time	Memory
78955		Charis02	Paprike (COI18_paprike)	C++14	100 / 100	90 ms	46184 KiB

paprike

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7

using namespace std;

ll n,k,h[N],cuts,a,b;
ll val[N];
vector < vector < ll > > graph(N);

void calc(ll cur,ll par)
{
    priority_queue < ll > pq;

    rep(i,0,graph[cur].size())
    {
        if(graph[cur][i] == par)
            continue;

        calc(graph[cur][i],cur);
        pq.push(-val[graph[cur][i]]);
    }

    val[cur] = h[cur];

    while(!pq.empty())
    {
        ll to_add = -pq.top();
        pq.pop();

        if(to_add + val[cur] > k)
            break;

        cuts--;
        val[cur] += to_add;
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> k;

    rep(i,1,n+1)
    {
        cin >> h[i];
    }

    rep(i,0,n-1)
    {
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    cuts = n-1;
    calc(1,1);

    cout << cuts << endl;

    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void calc(long long int, long long int)':
paprike.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
paprike.cpp:27:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
paprike.cpp:27:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~

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