Submission #331878

#	Time	Username	Problem	Language	Result	Execution time	Memory
331878		johutha	Paprike (COI18_paprike)	C++17	100 / 100	77 ms	19584 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>

#define int int64_t

using namespace std;

struct tree
{
    int k;
    vector<vector<int>> adjlist;
    vector<int> vs;

    int res = 0;
    
    int dfs(int curr, int par)
    {
        vector<int> poss;

        for (auto i : adjlist[curr])
        {
            if (par == i) continue;
            int cv = dfs(i, curr);
            poss.push_back(cv);
        }

        sort(poss.begin(), poss.end());
        int cnt = vs[curr];
        for (auto v : poss)
        {
            if (v + cnt <= k)
            {
                cnt += v;
            }
            else
            {
                res++;
            }
        }
        return cnt;
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;

    tree t;
    t.adjlist.resize(n);
    t.vs.resize(n);
    t.k = k;

    for (int i = 0; i < n; i++) cin >> t.vs[i];

    for (int i = 0; i<  n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        t.adjlist[a].push_back(b);
        t.adjlist[b].push_back(a);
    }

    t.dfs(0, -1);

    cout << t.res << "\n";
}

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