제출 #1293806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293806		mahmudisali	Paprike (COI18_paprike)	C++20	100 / 100	34 ms	21504 KiB

paprike

// Designed by Mahmud Isali
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #else
// #define debug(...)
// #endif

using pii = pair<int,int>;
using db = double;
using dbl = long double;

#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fastio() ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define newl cout << endl;


template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>using ordered_multiset = tree<pair<T,int>, null_type, less<pair<T,int>>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>int sz(const T& x) { return (int)x.size(); }
template<class T>int upper_index(const vector<T> &a, const T &x) {return (int)(upper_bound(all(a), x) - a.begin());}
template<class T>int lower_index(const vector<T> &a, const T &x) {return (int)(lower_bound(all(a), x) - a.begin());}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int  INF  = (int)4e18;
const int  MOD  = 1000000007;
const int  MOD2 = 998244353;
const int  N = 32768;
const dbl  EPS  = 1e-12;
void solve() {
    int n,m;
    cin >> n >> m;
    vector<int> a(n + 1, 0);
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int ans = 0;
    vector<int> s(n + 1, 0);
    function<void(int, int)> dfs = [&](int node, int par){
        vector<int> t;
        for(auto to : adj[node]) {
            if(to == par) 
                continue;
            dfs(to, node);
            t.pb(s[to]);
        }
        sort(all(t));
        s[node] = a[node];
        for(int i = 0; i < t.size(); i++) {
            if(s[node] + t[i] <= m) 
                s[node] += t[i];
            else 
                ans++;
        }
    };
    dfs(1,0);
    cout << ans;
}
signed main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
//     freopen("error.txt","w",stderr);
// #endif
    fastio();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Test Case: " << i << endl;
        solve();
    }
}

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