Submission #71438

#	Time	Username	Problem	Language	Result	Execution time	Memory
71438		aklo	Paprike (COI18_paprike)	C++14	13 / 100	173 ms	27900 KiB

paprike

#include<vector>
#include<iostream>
#include <cstdlib>
#include<queue>
#include <cassert>
using namespace std;

int niz[100005],niz1[100005],niz2[100005];
vector <int> v[100005];
int bio[100005];
int br=0;
int n,k;
int w=0;
int zbr[100005];
vector <int> q;
int r=0;
int b;

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

int main () {
	
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>niz[i];
	}
	for(int i=1; i<=n-1; i++){
		cin>>niz1[i]>>niz2[i];
		v[niz1[i]].push_back(niz2[i]);
		v[niz2[i]].push_back(niz1[i]);  
	}
	dfs(1);
	//cout<<"1234567"<<endl;
	cout<<br;
	//system("pause");
	
	
	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int)':
paprike.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v[x].size(); i++){
                ~^~~~~~~~~~~~
paprike.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(q.size()<r-1){
        ~~~~~~~~^~~~
paprike.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v[x].size(); i++){
                ~^~~~~~~~~~~~
paprike.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<q.size(); i++){
                ~^~~~~~~~~

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