oj.uz

Submission #71573

# Submission time Handle Problem Language Result Execution time Memory
71573 2018-08-25T07:26:15 Z aklo Paprike (COI18_paprike) C++14
13 / 100
 177 ms 14116 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2680 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 177 ms 12908 KB Output is correct
2 Correct 157 ms 13956 KB Output is correct
3 Correct 152 ms 14000 KB Output is correct
4 Correct 146 ms 14000 KB Output is correct
5 Correct 152 ms 14004 KB Output is correct
6 Correct 159 ms 14004 KB Output is correct
7 Correct 142 ms 14116 KB Output is correct
8 Correct 115 ms 14116 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2680 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 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -