Submission #640575

#	Time	Username	Problem	Language	Result	Execution time	Memory
640575		Hiennoob123	Paprike (COI18_paprike)	C++14	100 / 100	52 ms	21452 KiB

paprike

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
vector<ll> T[300005] ;
bool check[300005] ;
ll val[300005] ;
ll A[300005] ;
ll n , k ;
ll ans = 0 ;
void dfs(ll v , ll par)
{
    vector<ll> save ;
    val[v] = A[v] ;
    for(int i = 0 ; i< T[v].size() ; i++)
    {
        if(T[v][i]==par) continue ;
        dfs(T[v][i] , v) ;
        save.push_back(val[T[v][i]]) ;
    }
    sort(save.begin() , save.end()) ;
    for(int i = 0 ; i< save.size() ; i++)
    {
        if(val[v]+save[i]>k)
        {
            ans++ ;
        }
        else val[v] += save[i] ;
    }
}
void solve()
{
    cin >> n>> k ;
    for(int i = 1 ; i<= n ; i++) cin >> A[i] ;
    for(int i = 1 ; i< n ; i++)
    {
        ll a,  b ;
        cin >> a >> b ;
        T[a].push_back(b) ;
        T[b].push_back(a) ;
    }
    dfs(1 , 0) ;
    cout << ans ;
}
signed main()
{
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
    //freopen("IN.txt","r",stdin) ;
    //freopen("LINES.inp" , "r" , stdin) ;
    //freopen("LINES.out" , "w" , stdout) ;
    //freopen("OUT.txt" , "w" , stdout) ;
    int t = 1 ;
    //cout << t << " " << n << "\n" ;
    for(int i = 1 ; i<= t ; i++)
    {
        solve();
    }
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(long long int, long long int)':
paprike.cpp:23:22: 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]
   23 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
paprike.cpp:30:22: 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]
   30 |     for(int i = 0 ; i< save.size() ; i++)
      |                     ~^~~~~~~~~~~~~

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