/ SeriousOJ /

Record Detail

Runtime Error


  
# Status Time Cost Memory Cost
#1 Runtime Error double free or corruption (out) 1ms 548.0 KiB
#2 Runtime Error double free or corruption (out) 1ms 580.0 KiB
#3 Runtime Error double free or corruption (out) 1ms 552.0 KiB
#4 Runtime Error double free or corruption (out) 2ms 556.0 KiB
#5 Runtime Error double free or corruption (out) 24ms 2.59 MiB
#6 Runtime Error double free or corruption (out) 23ms 2.723 MiB
#7 Runtime Error double free or corruption (out) 25ms 2.719 MiB
#8 Runtime Error double free or corruption (out) 1ms 484.0 KiB
#9 Runtime Error double free or corruption (out) 2ms 764.0 KiB
#10 Runtime Error double free or corruption (out) 15ms 1.973 MiB
#11 Runtime Error double free or corruption (out) 26ms 3.066 MiB
#12 Runtime Error double free or corruption (out) 13ms 1.629 MiB
#13 Runtime Error double free or corruption (out) 31ms 3.266 MiB
#14 Runtime Error double free or corruption (out) 22ms 2.637 MiB
#15 Runtime Error double free or corruption (out) 2ms 532.0 KiB
#16 Runtime Error double free or corruption (out) 29ms 3.066 MiB
#17 Runtime Error double free or corruption (out) 28ms 3.066 MiB
#18 Runtime Error double free or corruption (out) 28ms 3.191 MiB
#19 Runtime Error double free or corruption (out) 147ms 18.871 MiB
#20 Runtime Error double free or corruption (out) 148ms 18.711 MiB
#21 Runtime Error double free or corruption (out) 149ms 18.883 MiB
#22 Runtime Error double free or corruption (out) 195ms 35.586 MiB
#23 Runtime Error double free or corruption (out) 202ms 18.531 MiB
#24 Runtime Error double free or corruption (out) 208ms 18.363 MiB
#25 Runtime Error double free or corruption (out) 176ms 18.918 MiB
#26 Runtime Error double free or corruption (out) 10ms 1.875 MiB

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long int;

void fastio(){ios::sync_with_stdio(false);cin.tie(0);}

vector<ll> take_inputs_0(ll n){vector<ll> v(n);for(int i=0;i<n;i++){cin>>v[i];}return v;}
vector<ll> take_inputs_1(ll n){vector<ll> v(n);for(int i=1;i<n;i++){cin>>v[i];}return v;}

void show(auto x){ cout<<x<<"\n";}
void show1(auto v){ ll n=(signed)v.size();for(int i=0;i<n;i++){cout<<v[i]<<" ";}cout<<"\n";}
void show2(auto v){ ll n=(signed)v.size();for(int i=0;i<n;i++){	cout<<v[i]<<"\n";}}

void sort_it(auto &v){ sort(v.begin(),v.end());}
void reverse_it(auto &v){ reverse(v.begin(),v.end());}
void do_both(auto &v){ sort(v.begin(),v.end());reverse(v.begin(),v.end());}

auto find_max(auto v){ sort(v.begin(),v.end());reverse(v.begin(),v.end());return v[0];}
auto find_min(auto v){ sort(v.begin(),v.end());return v[0];}

vector<ll> bitRep64(ll n){vector<ll> v;int i=0;while(i<=63){if(n&(1LL<<i)){v.push_back(1);}else{v.push_back(0);}i++;}return v;}
vector<ll> bitRep32(ll n){vector<ll> v;int i=0;while(i<=31){if(n&(1LL<<i)){v.push_back(1);}else{v.push_back(0);}i++;}return v;}
vector<string> all_subset(ll n){vector<string> v;for(int i=0;i<(1<<n);i++){string st="";for(int j=0;j<n;j++){if(i&(1<<j)){st+="1";}else{st+="0";}}v.push_back(st);}return v;}

vector<ll> prefix_sum_0(vector<ll> v){ll n=(signed)v.size();for(int i=1;i<n;i++){v[i]=v[i-1]+v[i];}return v;}
vector<ll> prefix_sum_1(vector<ll> v){ll n=(signed)v.size();vector<ll> summ(n+1);for(int i=1;i<=n;i++){summ[i]=summ[i-1]+v[i-1];}return summ;}

///////////////////////////////////

ll ans=0;
ll n;
ll done=0;

ll res=0;
void dfs(ll node,vector<ll> adj[],ll visited[],ll cnt[],ll restricted[])
{
	visited[node]=1;
	
	ll countt=0;
	
	for(auto x:adj[node])
	{
		if(!visited[x])
		{
			countt+=cnt[x]+1;
			cnt[node]+=countt+1;
			dfs(x,adj,visited,cnt,restricted);
		}
	}
	cnt[node]+=countt;
	
	if(cnt[node]==0)
	{
		restricted[node]=1;
	}
}

ll dfs2(ll node,vector<ll> adj[],ll visited[],ll cnt[],ll restricted[])
{
	visited[node]=1;
	res=ans;
	for(auto x:adj[node])
	{
		if(!visited[x] && restricted[x]==0)
		{
			if(done<n){ans++;}
			done++;
			dfs2(x,adj,visited,cnt,restricted);
		}
	}
	if(done<n){ans++;}
	//show(ans);
}


int main()
{
	int t;cin>>t;
	
	while(t--)
	{
		n;cin>>n;
		
		vector<ll> v(n+1);
		
		ll visited[n+1];
		ll cnt[n+1];
		
        ll restricted[n+1];
        
        ans=0;
        done=0;
		for(int i=1;i<=n;i++)
		{
			cin>>v[i];
			visited[i]=0;
			restricted[i]=0;
			cnt[i]=v[i];
		}
		
		vector<ll> adj[n+1];
		
		for(int i=0;i<n-1;i++)
		{
			ll x,y;cin>>x>>y;
			
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		
		ll node=-1;
		
		
		for(int i=1;i<=n;i++)
		{
			if(v[i]==1)
			{
				node=i;
				break;
			}
		}
		
		
		dfs(node,adj,visited,cnt,restricted);
		
		
		for(int i=1;i<=n;i++)
		{
			visited[i]=0;
			cnt[i]=0;
			
		}
		
		
		dfs2(node,adj,visited,cnt,restricted);
		
		show(res);
		
		
	}
	
	return 0;
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 17:20:10
Judged At
2024-10-03 13:22:24
Judged By
Score
0
Total Time
208ms
Peak Memory
35.586 MiB