Submission #1119146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119146		vjudge1	Paprike (COI18_paprike)	C++14	100 / 100	65 ms	21912 KiB

paprike

/*
=======-==========---=-----------------------=-==================-==-=-=-===------------------------------------------------------
---------=--==-------------------------------=----========-----==--=-----=--------------------------------------------------------
--------=====-======-----------=-------------------=---=----=======-------==--------------------:---------------------------------
-------=----===--------------------=-------------==-----------=--------------=---------:-::-:::::::::::::::::::::::::---:::::-:::-
----------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------:------:-------------------:::--------:-------------------:-:-
---------------:----------------------------------------:------------------------------------:::::::::::::::::----:::-::----------
--------:-::---:::-::::-----------::::::-:---:------:::::--------------:--------::--::::-:::::::::::::::::::::::::::::::-:::------
-------------------:::::::--------::-:::::::::---=+***++=++=----------:--::::::--:::::::-:::------:::--:::::---::::::::::---------
:::::::-::::--:::::::::::::::::::::::::::::--#%%@@@@@@@@@@@%+----------::------:::::::::::::::::-:-:-::::::::::::::-::-:---::-::--
::-:::::::---::::::::::----:--:-:-:::::---:=%@@@@@@@@@@@@@@@@*=--+------:::::::::::::::::::-::-:::--------:::::::::-::::::--------
::::::-:::::::::::::::::::::::::::::::::::-*%@@@@@@@@@@@@@@%*=*@@@@#+=-:::::::::::::::::::::::::::::::-::=*%%@@@@%#*=--::--::-----
::::::::::::::::::::::::::::::::::::::::::+#=%@@@@@@@@@@@@@@%@@@@@@@%#+=----:::::::::::::::::::::::::::=%@@@@@@@@@@@@%=::---------
::::::::::::::::::::::::::::--::::::::::::-@*+@@@@@@@@@@@@@@@@@@@%*+==========------::::::::::::::::::+@@@@@@@@@@@@@@@@+::-----:::
::::::::::::::::::::::::::::-------------::-+:=#%@%%%@@%@@@@@@@@*+=========+=========-::::::::::::::-*@@@@@%@%%%%%#%@@@@*-::::::::
:::::::::-:::::::::::::::::::::::::::::::::::-*#######%%@@@@@@@+=+++++++++***++*+**++*+:::::::::::==#@@@@@@@@@@@@@@%%#@@@+:::::::-
:::::::::::::::::::::::::::::::::::::::::::::-:--%%###%%@@@@@@%#**#****#%%%%%#%%####****-::::::::-+%@@@@@@@@@@@@@@@%@@@@@@=:------
:::::::::::::::.:::::::::::::::::::::::::::::::::++###%@@@@@%%%%%@%%###%%@@@@@@@@@@@%%###+::::::::%@@@@@@@@@@@@@@%**@@@@@@@=::::::
::::::::::::::..........::::::::::::::::::::::::::::-*%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%#:..::=%@@@@@@@@@@@@@@@@@@@@@@@@@@=:::::
:::::::::::::::::::.::::::::::::::::::::::::::::::::::---%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:.=#@@%#%@@@@@@@@@@@@@@@@@@@@@@@@*:::.
:::::::::::::::::::::::::::::::::::::::.....:::.........@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#.:+%@@@@@@%#*+========++**###@@#*=...
:::::::::::::::::::::::::::::::::::::::::.:::.:.........%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#..:+*#%@@@@@@@@@@@@@@@@@@@@@@@#+:...
::::::::::::::::::...:...:::..::.:....:......:+-........+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#......:=**#%%%%%%%%@%%##*+=::::....
::::::::::::::::.............................-=:..::...-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#...........:-=:..............::::.
.....::::::::.............................:-:........:.*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:........+*#+..............::..:-
......:..::..:..........................::--:........::#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-...:=++#%@=====:...............
:::.:::::::::::........................::::---::...::.:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+*:-+=++#%#+++*++***+=::.......:
::.:::::::::::..:...................::::::--=-:......*@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@**-=+++#%*++**+=--=+++**+-:...=
::::::::.....:......::...........:::::::-::---::::::=@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@*#+=++*#+++****+==+===+++**=-.
:.:..:::::.:::.................:::::::-:::----:-:::-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*##++**++****###%%#*++***+===
:::::::::::::.::...............:--::--::::====-::=+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@*#****+***##*#%%#***=+===
:::::::::::::.::.:..:..........:::::---:::--=---==%@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%##%##**++*#******++++++
..........................:::::..::::--:---==--:%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#***#%######**+
.......::...............:::.:.....:::----====-:.@@@@@@@@@@@@@%%@@@%#%@@%@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######*+:::---:
......::::::::::::::.::.::.:....::::....--+-*=::@@@@@@@@@@-....+%%%##%@@@%%%%%@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@=-==---=-:.........
...:::::::.:::::::.:::.:........::......::::-:..-=+*#%@@@@#+-::-%@@@%%%%%#%@@@@@@@**%@@@@@@@@@@@@@@@@@@@@@@@@@#:-:..............::
::::::::::::::::.:-=-::........:::............:::=....-=+*##%%%%@@@@@@@@@@@@@@@@@%+*+@@@@@@@@@@@@@@@@@@@@@@@@@:..-:.......:-:----:
:::::::::::::::.:-==:.........::..::-::....-=++*++*+++=+++*#@@@@@@@@@@@@@@@%%@@@@@#@#@@@@@@@@@@@@@@@@@@@@@@%%+.............:-=-:..
.::::::::::::..---=-:::.::.::----=**++=..:==***@%%%%%###*#%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=::....................
..::::::::::::=====-:::::::--*++=*#**#*..=+**#%@@@%%@%%%#%%%%%@@@@@%@@@@@%%@@@@@@@@@%@@%%%@@@@@@@@@@@@@@@@*..........:::.::.......
:::::::::.::-=+====-:::..::=*####**#%%#..=#**%%%@@@@%%%%%%%%@%%%%%@@@@@%@%%@%%%%%%@%%%%%%%%@@@@@@@@@@@@@@@%-:...........--*#*++---
:::::::::::::-===--:::::::--=*%%%%@@@%#.:=+#%%%@@@@%***##%%@@@@@@@@%%@%@@@@@@%%%#%%%###%%%@@@@@@@@@@@@@@@@@%%#*#=-:..........:...-
::::::::::::::::==--::::-===*##%@@@@@%+.=######%%#+#*++++#%++#%%%%@%%@@@@@@@@@@@@@@@%@@@%@@@@@@@@@@@@@@@@@@%%@@@@@*=++==***=-:::-#
.:.::..:::::::::..::::::-+**#%@@@@@@@@=:+###%#%#*==#*****#%+.:*####*=#%%%%%@%%@%%#####**%%%@@@@@@@@@@@@@@@@*@@@@%#%*+*%@@@@@@%#**%
::::::::::::::.....:---==+###%@@@@@@@@=-##%%%###*==##%#####+.:+###*+=%%%%#%**%%#*****+*#%%@@@@@@@@@@@@@@@@@@%@@%%@##%#%%%%%@@@%##*
::::::...::---+:.....=+=*%#%@@@@%%@@@@=+##%%####*=#%@%%%#%%#..=*#*+-#@@@%#++*##*+*=::-*%@@@@@%%#@@@@@@@@@@@@@%#%@@@%%%%@@@%@@@@%#*
:--=-..:=----=-.......=##@@@@@@@@@@@@@**###%####**@@@@@@@@%%..-*#+:#@@@@*=+=:+-:..::=#%%@@%##**@%@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@#
........-++*%=....::::..=%@@@@@@@@@@@@**#######*#@@@@@@@@@@#..:+*-+@@@@%+::.:...--:+%%@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
----+*++**##%+=-..:.:+#*##@@@@@@@@@@@@+#######*#@@@@@@@@@@@+..-++:@@@@#-...::.-=::=%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@
###%*++#@@%@%***%@@%###@@@@%%@@@@@@@@@+########@@@@@@%@@@@@:..-*=+@@@#-:.....:-+**#*#%@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@%%
#===+#%@@@@@@%%@@@@%@@%*-.+:..:+@@@@@%*######*-.:=::..==---..:-*+:.:---...-:=*+=+*###%@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@
.:-::..:-==:...-==-=...........:--::.:######*:..............:=*##*::-=-..-:.=++=*%%%%@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@
.:::--:::-=-.........................=*#####+..........:...-*%@@@+-+@-..:...:=#%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#++=--::-=+@@@@@@@@@@
:::==+****+-:.......................:*######+........+#%*%@@@@@@#-:-#=-#=:.:*%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+=++=++=*##%+@@@@@@@@@
.....:=++**=:..:.:..................-*#%######:.......::+%@@@%#++=-=+%#=..**%%%%@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@%+@@@@@@@@
.........-:...:-...................:+#%##%%%@@%:.........--::::##==.....:-=*##%%##%@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@%@@@@@@++@@@@@@@
::................................-+*#%%%@@@@@@+......:..:::-:-==.....:+=++*######@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@*#@@@@@@
...........................:-=+=..=*%@@@@@@@@%=...:........---+*=:..:=+-*#@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@
........................-##=*%@@@@@@@@@%+-:+@@#-..:--::::...:=+::==**#*#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
:......................:++===##%%%%%*=:..-#**%#**--**-::..=*##==*%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
=-..................................::---==+=:::-+#%@%%##%%#@@@#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+*-...............................................-#@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-=*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
............................................:+#*==+--=----=*##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%++=....:+@@@@@@@@@@@@@@@@@@@%%%*+-.:--
*/
// Ahmadov orz
/// successful failure
#include <bits/stdc++.h>
/// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
/// using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define drop(x) cout<<x<<endl;return
// template <class T>
// using isTree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/// sometimes you gotta think simple
struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};
const int N = 1e5 + 7;
vector <int> g[N];
int val[N];
int dp[N];
int ans = 0;
void dfs(int node, int par = -1, int k = 0)
{
    priority_queue <int> pq;
    //vector <int> subtrees;
    dp[node] = val[node];
    for (auto v:g[node]) {
        if (par != v) {
            dfs(v, node, k);
            dp[node] += dp[v];     // dfs atandan sonra et!!!
            pq.push(dp[v]);        // dfs atandan sonra et!!!
            //subtrees.pb(v);
        }
    }
    // cout << "node: " << node << endl;
    // cout << "subtree: ";
    // for (auto u:subtrees) {
    //     cout << u << " ";
    // }
    // cout << endl;
    // cout << endl;
    while (!pq.empty() && dp[node] > k) {
        ans++;
        dp[node] -= pq.top();
        pq.pop();
    }
}
void failure()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, -1, k);
    // cout << "! ";
    // for (int i = 1; i <= n; i++) {
    //     cout << dp[i] << " ";
    // }
    // cout << endl;
    drop(ans);
} 
signed main() {  
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL);                
    cout.tie(NULL);
    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        failure();
    }
}

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