Submission #566096

#	Time	Username	Problem	Language	Result	Execution time	Memory
566096		bkosmacin	Paprike (COI18_paprike)	C++14	100 / 100	56 ms	14824 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1);

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define all(a) (a).begin(),(a).end()
#define fi first
#define sz(a) (a).size()
#define se second
#define DEGTORAD(D)((D * PI) / 180.0)
#define RADTODEG(R)((180.0 * R) / PI)

ll dx[]={0,0,1,-1},dy[]={1,-1,0,0};
const ll N = 1e5+5;
ll n,k,h[N],otec[N],klk[N];
vector<ll> graf[N];

void dfs(ll x,ll y){
	otec[x] = y;
	for (ll i=0;i<graf[x].size();i++){
		if (graf[x][i]==y){
			continue;
		}
		dfs(graf[x][i],x);
	}
}

void solve(){
	cin >>n>>k;
	memset(klk,0,sizeof(klk));
	for (ll i=0;i<n;i++){
		cin >>h[i];
	}
	for (ll i=0;i<n-1;i++){
		ll x,y;
		cin >>x>>y;
		x--;y--;
		graf[x].pb(y);
		graf[y].pb(x);
	}
	dfs(0,-1);
	for (ll i=1;i<n;i++){
		if (graf[i].size()>1){
			klk[otec[i]]++;
		}
		if (graf[i].size()==1){
			klk[i]=-1;
		}
	}
	queue<ll> q;
	for (ll i=0;i<n;i++){
		if (klk[i]==0){
			q.push(i);
		}
	}
	ll sol = 0;
	while (!q.empty()){
		
		ll tren = q.front();
		q.pop();

		vector<ll> pom;
		for (ll i=0;i<graf[tren].size();++i){
			if (graf[tren][i]==otec[tren]){
				continue;
			}
			pom.pb(h[graf[tren][i]]);
		}
		ll pug = 0;
		sort(all(pom));
		for (ll i=0;i<sz(pom);i++){
			if (h[tren]+pom[i]<=k){
				h[tren]+=pom[i];
			}else{
				sol+=sz(pom)-i;
				pug = sz(pom)-i;
				break;
			}
		}
	//	cout <<tren+1<<' '<<h[tren]<<' '<<pug<<endl;
		klk[otec[tren]]--;
		if (klk[otec[tren]]==0){
			q.push(otec[tren]);
		}
	}
	cout <<sol<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t=1;
   // cin >>t;
    while (t--){
        solve();
    }

    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(long long int, long long int)':
paprike.cpp:24:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (ll i=0;i<graf[x].size();i++){
      |              ~^~~~~~~~~~~~~~~
paprike.cpp: In function 'void solve()':
paprike.cpp:67:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (ll i=0;i<graf[tren].size();++i){
      |               ~^~~~~~~~~~~~~~~~~~
paprike.cpp:75:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (ll i=0;i<sz(pom);i++){
      |                ^
paprike.cpp:73:6: warning: variable 'pug' set but not used [-Wunused-but-set-variable]
   73 |   ll pug = 0;
      |      ^~~

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