Submission #640580

#	Time	Username	Problem	Language	Result	Execution time	Memory
640580		Tuanlinh123	Paprike (COI18_paprike)	C++17	100 / 100	68 ms	17568 KiB

paprike

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/freopen/"

vector <ll> A[100005];
ll a[100005], cut[100005], rem[100005];
ll n, k;

void solve(ll s, ll pa)
{
    rem[s]=a[s];
    vector <ll> num;
    for (ll i=0; i<A[s].size(); i++)
    {
        ll v=A[s][i];
        if (v==pa)
            continue;
        solve(v, s);
        cut[s]+=cut[v];
        num.pb(rem[v]);
    }
    sort(num.begin(), num.end());
    for (ll i=0; i<num.size(); i++)
    {
        if (rem[s]+num[i]>k)
            cut[s]++;
        else rem[s]+=num[i];
    }
}


int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n >> k;
    for (ll i=1; i<=n; i++)
        cin >> a[i];
    for (ll i=1; i<n; i++)
    {
        ll x, y; cin >> x >> y;
        A[x].pb(y); A[y].pb(x);
    }
    solve(1, 1);
    // for (ll i=1; i<=n; i++)
    //     cout << cut[i] << " " << rem[i] << "\n";
    cout << cut[1];
}

Compilation message (stderr)

paprike.cpp: In function 'void solve(long long int, long long int)':
paprike.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (ll i=0; i<A[s].size(); i++)
      |                  ~^~~~~~~~~~~~
paprike.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (ll i=0; i<num.size(); i++)
      |                  ~^~~~~~~~~~~

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