제출 #1311593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311593		HoriaHaivas	Paprike (COI18_paprike)	C++20	100 / 100	38 ms	19060 KiB

paprike

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct info
{
    int cuts;
    int compsize;
};

info dp[100005];
int s[100005];
int k;
vector<int> nodes[100005];
vector<int> nush;

void dfs(int node, int parent)
{
    int taieri,compsz;
    taieri=0;
    compsz=s[node];
    for (auto x : nodes[node])
    {
         if (x!=parent)
         {
             dfs(x,node);
             taieri+=dp[x].cuts;
             compsz+=dp[x].compsize;
         }
    }
    nush.clear();
    for (auto x : nodes[node])
    {
         if (x!=parent)
         {
             nush.push_back(dp[x].compsize);
         }
    }
    if (compsz<=k)
    {
        dp[node].cuts=taieri;
        dp[node].compsize=compsz;
    }
    else
    {
        sort(nush.begin(),nush.end());
        while(compsz>k)
        {
            taieri++;
            compsz-=nush.back();
            nush.pop_back();
        }
        dp[node].cuts=taieri;
        dp[node].compsize=compsz;
    }
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,u,v;
    cin >> n >> k;
    for (i=1;i<=n;i++)
         cin >> s[i];
    for (i=1;i<=n-1;i++)
    {
         cin >> u >> v;
         nodes[u].push_back(v);
         nodes[v].push_back(u);
    }
    dfs(1,-1);
    cout << dp[1].cuts;
    return 0;
}

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