Submission #168058

#	Time	Username	Problem	Language	Result	Execution time	Memory
168058		Atill83	Paprike (COI18_paprike)	C++14	100 / 100	71 ms	18808 KiB

paprike

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, k;
vector<int> adj[MAXN];
ll hot[MAXN];
pll dfs(int a, int par){
    if(adj[a].size() == 1 && par != -1){
        return {hot[a], 0};
    }else{
        vector<pll> ans;
        ll eko = 0;
        for(int i: adj[a]){
            if(i != par){
                pll dat = dfs(i, a);
                eko += dat.ss;
                ans.push_back(dat);
            }
        }
        sort(ans.begin(), ans. end());
        ll cur = hot[a];
        int i = 0;
        for(; i < ans.size(); i++){
            if(cur + ans[i].ff > k){
                break;
            }else{
                cur = cur + ans[i].ff;
            }
        }
        return {cur, eko + ans.size() - i};
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n>>k;
    for(int i = 1; i <= n; i++) cin>>hot[i];
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ll ans = INF;
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 generator (seed);  
    for(int i = 0; i < 1; i++){
        ll a = generator()%n + 1;
        //cout<<a<<endl;
        ans = min(ans, dfs(a, -1).ss);
    }
    cout<<ans<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

paprike.cpp: In function 'pll dfs(int, int)':
paprike.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; i < ans.size(); i++){
               ~~^~~~~~~~~~~~

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