Submission #1127544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127544		cpismayilmmdv985	Paprike (COI18_paprike)	C++20	13 / 100	47 ms	20804 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>ostream& operator<<(ostream &os, const pair<T1, T2> &p) {return os << '{' << p.first << ", " << p.second << '}';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& m) {os << "{";for (auto it = m.begin(); it != m.end(); ++it) {if (it != m.begin()) os << ", "; os << it->first << " : " << it->second;}return os << "}";}
void debug() { cerr << endl; }
template<typename Head, typename... Tail>
void debug(Head H, Tail... T) { cerr << H; debug(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", debug(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const int dx4[] = {1, -1, 0, 0}, dy4[] = {0, 0, -1, 1};
const int dx8[] = {1, -1, 0, 0, 1, -1, 1, -1}, dy8[] = {0, 0, -1, 1, 1, -1, -1, 1};

set<int> g[mxN];
set<array<int64_t, 2>> leaf;
int64_t arr[mxN], cost[mxN];

void run_case() {
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)    cin >> arr[i], cost[i] = arr[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].insert(v);
        g[v].insert(u);
    }
    for (int i = 1; i <= n; i++)
        if (g[i].size() == 1)
            leaf.insert({arr[i], i});
    while (!leaf.empty()) {
        int64_t u = (*leaf.begin())[1], c = (*leaf.begin())[0];
        leaf.erase({c, u});
        if (!g[u].empty()) {
            auto v = *g[u].begin();
            g[u].clear();
            g[v].erase(u);
            if (cost[v] + cost[u] <= k) {
                cost[v] += cost[u];
            } else {
                ans++;
            }
            if (g[v].size() == 1) {
                leaf.insert({cost[v], v});
            }
        }
    }
    cout << ans << "\n";
    // for (int i = 1; i <= n; i++)    cout << cost[i] << " ";
    return;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int test_case = 1;
    // cin >> test_case;
    for (int num_case = 1; num_case <= test_case; num_case++) {
        run_case();
    }
    return 0;
}

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