oj.uz

Submission #71438

# Submission time Handle Problem Language Result Execution time Memory
71438 2018-08-24T15:24:33 Z aklo Paprike (COI18_paprike) C++14
13 / 100
 173 ms 27900 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 14580 KB Output is correct
2 Correct 167 ms 16648 KB Output is correct
3 Correct 172 ms 18564 KB Output is correct
4 Correct 173 ms 20588 KB Output is correct
5 Correct 152 ms 22612 KB Output is correct
6 Correct 157 ms 24644 KB Output is correct
7 Correct 137 ms 26416 KB Output is correct
8 Correct 132 ms 27900 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -