Submission #318466

#	Time	Username	Problem	Language	Result	Execution time	Memory
318466		penguin71630	Paprike (COI18_paprike)	C++14	100 / 100	71 ms	15972 KiB

paprike

#include <bits/stdc++.h>

#define Optimize ios_base::sync_with_stdio(false); cin.tie(0);
#define F first
#define S second
#define mp(a, b) make_pair(a, b)
#define iter(a) a.begin(), a.end()
#define ariter(_a, _n) _a, _a+_n
#define dbg(a, b) cout << "var " << a << " -> " << b << '\n';
#define dbg_itv(l, r, val) cout << "### (" << l << ", " << r << ") -> " << val << '\n';
#define flag(_a) cout << "Still alive at flag " << _a << '\n';
#define printv(_a) for (auto& _i : _a) cout << _i << ' '; cout << '\n';
#define printchar(_c, _n) for (int i = 0; i < _n; i++) cout << _c;
#define clear_stk(_s) while (!_s.empty()) _s.pop();
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 1;
const int lgmx = 17;
const int INF = 2147483647;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int n, ans = 0;
ll k;
vector<int> G[maxn];
vector<ll> val;

ll dfs(int u, int pa) {
    ll sz = val[u];
    priority_queue<int> kids;
    for (auto& i : G[u]) {
        if (i == pa) continue;
        ll kid = dfs(i, u);
        sz += kid;
        kids.push(kid);
    }
    while (!kids.empty() && sz > k) {
        sz -= kids.top();
        ans++;
        kids.pop();
    }
    return sz;
}

int main() {
    Optimize

    cin >> n >> k;
    val.resize(n);
    fill(ariter(G, maxn), vector<int>());

    for (auto& i : val) cin >> i;
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(0, -1);
    cout << ans << '\n';

    return 0;
}

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