Submission #71573

#	Time	Username	Problem	Language	Result	Execution time	Memory
71573		aklo	Paprike (COI18_paprike)	C++14	13 / 100	177 ms	14116 KiB

paprike

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

int n,k,r=0,b,br=0;
int niz[100005],zbr[100005],bio[100005];
pair <int, int> a[100005];
vector <int> v[100005];
vector <int> ve;

void dfs(int x){
	bio[x]=1;
	if(zbr[x]+niz[x]<=k){
		for(int i=0; i<ve.size(); i++){
			zbr[ve[i]]+=niz[x];
		}
		zbr[x]+=niz[x];
		if(r<ve.size()){
			ve[r]=x;
		}
		else{
			ve.push_back(x);
		}
		r++;
		for(int i=0; i<v[x].size(); i++){
			if(bio[v[x][i]]==0){
				zbr[v[x][i]]=zbr[x];
				dfs(v[x][i]);
			}
		}
	}
	else{
		br++;
		//cout<<x<<endl<<endl;
		b=ve.size();
		for(int i=0; i<b; i++){
			ve.pop_back();
		}
		r=0;
		zbr[x]=niz[x];
		ve.push_back(x);
		r++;
		for(int i=0; i<v[x].size(); i++){
			if(bio[v[x][i]]==0){
				zbr[v[x][i]]=zbr[x];
				dfs(v[x][i]);
			}
		}
	}
}

int main () {
	
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>niz[i];
	}
	for(int i=1; i<n; i++){
		cin>>a[i].first;
		cin>>a[i].second;
		v[a[i].first].push_back(a[i].second);
		v[a[i].second].push_back(a[i].first);
	}
	dfs(1);
	cout<<br<<endl;
	//for(int i=1; i<=n; i++){
	//	cout<<zbr[i]<<endl;
	//}
	
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int)':
paprike.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<ve.size(); i++){
                ~^~~~~~~~~~
paprike.cpp:20:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(r<ve.size()){
      ~^~~~~~~~~~
paprike.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v[x].size(); i++){
                ~^~~~~~~~~~~~
paprike.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v[x].size(); i++){
                ~^~~~~~~~~~~~

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