Submission #1128930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128930		zovumeluka	Paprike (COI18_paprike)	C++20	100 / 100	52 ms	22344 KiB

paprike

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define F first
#define S second
#define ld long double
#define endl "\n"
#define testcases \
	int test_amount;        \
	cin >> test_amount;       \
	while (test_amount--)
//#pragma GCC target("popcnt")
//priority_queue<pll,vector<pll>,greater<pll>> q;
//cout<<setprecision(X)<<fixed;
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
ll mod = 1e9+7;
ll inf = 1e18+5;
ll A = 1337;
ll gcd(ll a, ll b){return (b==0? a : gcd(b, a%b));}
ll pot(ll b,ll eks){
	ll r = 1;b%=mod;
	while(eks>0){if(eks%2)r=(r*b)%mod; b=(b*b)%mod;eks=eks/2;}
	return r;
}
int n,k,reza,v[200005],dp[200005][2],visited[200005];//dp[i][0]->kolko je ostalo od podstabla tog nodea
vector<int> adj[200005];
void dfs(int node){
	if(visited[node])return;
	visited[node]=1;
	vector<int> u;
	for(auto z : adj[node]){
		if(!visited[z]){
			dfs(z);
			u.push_back(dp[z][0]);
		}
	}
	sort(u.begin(),u.end());
	int zbroj = v[node];
	dp[node][1]=u.size();
	for(auto z : u){
		if(z<=k-zbroj){
			dp[node][1]--;
			zbroj+=z;
		}
		else break;
	}
	dp[node][0]=zbroj;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	for(int i = 1; i<=n; i++)cin>>v[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);
	}
	dfs(1);
	for(int i = 1; i<=n; i++)reza+=dp[i][1];
	cout<<reza<<endl;
return 0;
}

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