Submission #98761

#	Time	Username	Problem	Language	Result	Execution time	Memory
98761		popopo3124	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	40 ms	21240 KiB

uzastopni

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli N=100009, K=109;
lli n, a[N];
vector<lli> D[N];
void Inp()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		lli u, v;
		cin>>u>>v;
		D[u].push_back(v);
	}
}
lli l[N][K], r[N][K], dd1[N], dd2[N];
void DFS(lli u)
{
	for(auto v: D[u])
	{
		DFS(v);
	}
	l[u][a[u]]=1;
	r[u][a[u]]=1;
	for(int i=a[u];i>1;i--)
	{
		if(l[u][i]==0)
		{
			continue;
		}
		for(auto v: D[u])
		{
			if(dd1[v]||r[v][i-1]==0)
			{
				continue;
			}
			dd1[v]=1;
			for(int j=1;j<=100;j++)
			{
				if(l[v][j])
				{
					l[u][j]=1;
				}
			}
		}
	}
	for(int i=a[u];i<100;i++)
	{
		if(r[u][i]==0)
		{
			continue;
		}
		for(auto v: D[u])
		{
			if(dd2[v]||l[v][i+1]==0)
			{
				continue;
			}
			dd2[v]=1;
			for(int j=1;j<=100;j++)
			{
				if(r[v][j])
				{
					r[u][j]=1;
				}
			}
		}
	}
}
void Solve()
{
	DFS(1);
	lli cnt1=0, cnt2=0;
	for(int i=1;i<=100;i++)
	{
		if(l[1][i])
		{
			cnt1++;
		}
		if(r[1][i])
		{
			cnt2++;
		}
	}
	cout<<cnt1*cnt2;
}
int main()
{
	//freopen("test.inp","r",stdin);freopen("out.out","w",stdout);
	Inp();
	Solve();
}

• Subtask 1: 160 / 160