Submission #1095228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095228		FIFI_cpp	Paprike (COI18_paprike)	C++17	100 / 100	96 ms	43348 KiB

paprike

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<int,pair<int,int>>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
//const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 2003;
const int INF = -10000000000000000;
//ifstream fin("spirala.in");
//ofstream fout("spirala.out");
int spice[1000006];
int n,k;
vector<int> graph[1000006];
int c = 0;
bool visited[1000006];
int dp[1000006];
 
void dfs(int u)
{
    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});
        }
    }
    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 --;
    }
}
 
int32_t 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 << '\n';
}

Compilation message (stderr)

paprike.cpp:31:9: warning: "/*" within comment [-Wcomment]
   31 | /*   /\_/\
      |

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