Submission #956367

#	Time	Username	Problem	Language	Result	Execution time	Memory
956367		ZeroCool	Paprike (COI18_paprike)	C++14	0 / 100	39 ms	26960 KiB

paprike

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
      
using namespace std;
using namespace __gnu_pbds;
      
template <typename T>
using oset = tree<T,null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update>;
      
#define int long long
          
#define pb push_back
#define ins insert
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
  
          
using ll = long long;
using ld = long double;
  
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
        
#define da cout<<"DA"<<endl
#define ne cout<<"NE"<<endl
          
#define send ios::sync_with_stdio(false);
#define help cin.tie(0);
          
void solve(int T);
          
const int N = 3e5 + 10;
const int M = 5e5 + 10;
const int SQRT = sqrt(N);
const int LOG = 20;
const int INF = 1e18;
const int MOD = 123456789;
const ld EPS = 1e-9;
          
  
int ans;
int n, m,k, q, l, r, x, y, z, mx, mn;
  
  
          
int32_t main(){
    #ifndef ONLINE_JUDGE
        auto begin = chrono::high_resolution_clock::now();
    #endif
    cout<<setprecision(7)<<fixed;
              
    send help;
          
    int tt = 1;
  //cin>>tt; //? Comment if no testcases
    for(int i = 1;i<=tt;i++){
        #ifndef ONLINE_JUDGE
            cout<<"Case "<<i<<": "<<endl;
        #endif
        solve(i);
    }
    #ifndef ONLINE_JUDGE
        auto end = chrono::high_resolution_clock::now();
        cout<<"Time: "<<chrono::duration_cast<chrono::duration<double>>(end - begin).count()<<endl;
    #endif
    return 0;
}

int dp[N];

vector<int> g[N];

int A[N];

void dfs(int x,int p){
    dp[x] = A[x];
    vector<int> vec;
    for(auto u : g[x]){
        if(u == p)continue;
        dfs(u, x);
        vec.pb(dp[u]);
    }
    sort(all(vec));
    for(auto u : vec){
        if(dp[x] + u > k)ans++;
        else dp[x] += u;
    }
}

void solve(int T){
    cin>>n>>k;
    for(int i = 0;i<n;i++)cin>>A[i];
    for(int i =1 ;i<n;i++){
        int u, v;
        cin>>u>>v;
        --u, --v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(0, 0);
    cout<<ans<<endl;
}   
  
  
  
//Te molam da raboti !!

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