Submission #1091968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091968		clementine	Paprike (COI18_paprike)	C++17	100 / 100	123 ms	42792 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int spice[1000006];
int n, k;
vector<int> graph[1000006];
int c = 0;
bool visited[1000006];
ll dp[1000006];

void dfs(int u)
{
    //cout << u << " \n";
    visited[u] = true;
    vector<pair<ll ,int>> children;
    dp[u] += spice[u];
    for(auto v: graph[u])
    {
        if(!visited[v])
        {
            dfs(v);
            children.push_back({dp[v], v});
            //cout << dp[v] << "l ";
        }
    }
    //cout << '\n';
    int cnt = children.size();
    sort(children.begin(), children.end());
    for(auto p : children)
    {
        if(dp[u] + p.first > k)
        {
            //cout << cnt << " and " << c << '\n';
            c += cnt;
            break;
        }
        dp[u] += p.first;
        cnt --;
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        cin >> spice[i];
    }
    for(int i = 0; i < n-1; i ++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    cout << c;

}

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