제출 #1117586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117586		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	40 ms	18460 KiB

paprike

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1e5 + 5;
vector<ll> g[N];
ll a[N], cur[N], k, ans = 0;
void dfs(ll v, ll par = 0)
{
    vector<ll> vals;
    cur[v] = a[v];
    for (ll to : g[v])
        if (to != par) dfs(to, v), vals.push_back(cur[to]);
    sort(vals.begin(), vals.end());
    for (ll i : vals)
        if (i + cur[v] > k) ans++;
        else cur[v] += i;
}
void solve()
{
    ll n;
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i < n; i++)
    {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll t = 1;   
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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