Submission #241011

#	Time	Username	Problem	Language	Result	Execution time	Memory
241011		topovik	Paprike (COI18_paprike)	C++14	24 / 100	175 ms	17708 KiB

paprike

#include <bits/stdc++.h>

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define f first
#define s second
#define pb push_back
#define INF 1000000000
#define N (long)1e6

using namespace std;

typedef long long ll;
typedef long double ld;

vector <vector <int> > a;

int n,k;
int b[N];
int ans;

int Rec(int x, int y)
{
    vector <int> c;
    int sum=b[x];
    for (int i=0; i<a[x].size(); i++)
        if (a[x][i]!=y) c.pb(Rec(a[x][i],x)),sum+=c.back();
    sort(c.rbegin(),c.rend());
    for (int i=0; sum>k; i++) sum-=c[i],ans++;
    return sum;
}

int main()
{
    cin>>n>>k;
    for (int i=0; i<n; i++) cin>>b[i];
    a.resize(n);
    for (int i=0; i<n-1; i++)
    {
        int x,y;
        cin>>x>>y;
        a[--x].pb(--y);
        a[y].pb(x);
    }
    Rec(0,0);
    cout<<ans;
}

Compilation message (stderr)

paprike.cpp:3:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
paprike.cpp: In function 'int Rec(int, int)':
paprike.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<a[x].size(); i++)
                   ~^~~~~~~~~~~~

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