Submission #199324

#	Time	Username	Problem	Language	Result	Execution time	Memory
199324		kshitij_sodani	Paprike (COI18_paprike)	C++17	100 / 100	109 ms	18328 KiB

paprike

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long int llo ;
#define mp make_pair
#define pb push_back
#define a first
#define b second
vector<llo> adj[100001];
llo it[100001];
llo vis[100001];
pair<llo,llo> dp[100001];
llo ans;
vector<llo> stac;
llo n,k;


void dfs(llo no){
	llo co=it[no];
	dp[no]=mp(1,co);
	vector<pair<llo,llo>> aa;
	for(llo j=0;j<adj[no].size();j++){
		llo nn=adj[no][j];
		if(vis[nn]==0){
			vis[nn]=1;
			dfs(nn);
			aa.pb(mp(dp[nn].b,dp[nn].a));
		}
	}
	sort(aa.begin(),aa.end());
	llo st=0;
	for(llo i=0;i<aa.size();i++){
		if(co+aa[i].a<=k and st==0){
			co+=aa[i].a;
			dp[no].a+=aa[i].b-1;
		}
		else{
			st=1;
			dp[no].a+=aa[i].b;
		}
	}
	dp[no].b=co;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;

	memset(vis,0,sizeof(vis));
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}

	llo aa,bb;

	for(llo i=0;i<n-1;i++){
		cin>>aa>>bb;
		adj[aa-1].pb(bb-1);
		adj[bb-1].pb(aa-1);
	}
	vis[0]=1;
	dfs(0);
	cout<<dp[0].a-1<<endl;






	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(llo)':
paprike.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
paprike.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<aa.size();i++){
              ~^~~~~~~~~~

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