Submission #1293842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293842		saidshikhov	Paprike (COI18_paprike)	C++20	13 / 100	72 ms	10848 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> graph;
vector<int> spiciness;
vector<bool> visited;
int n, k;
int cuts = 0;

int dfs(int node, int parent) {
    visited[node] = true;
    
    int total = spiciness[node];
    
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        
        int subtree_sum = dfs(neighbor, node);
        
        if (total + subtree_sum <= k) {
            total += subtree_sum;
        } else {
            cuts++;
        }
    }
    
    return total;
}

int main() {
    cin >> n >> k;
    
    spiciness.resize(n);
    graph.resize(n);
    visited.assign(n, false);
    
    for (int i = 0; i < n; i++) {
        cin >> spiciness[i];
    }
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    dfs(0, -1);
    
    cout << cuts << endl;
    
    return 0;
}

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