oj.uz

Submission #98761

# Submission time Handle Problem Language Result Execution time Memory
98761 2019-02-25T16:53:08 Z popopo3124 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 40 ms 21240 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 4 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 31 ms 20352 KB Output is correct
12 Correct 40 ms 20280 KB Output is correct
13 Correct 34 ms 20344 KB Output is correct
14 Correct 38 ms 21240 KB Output is correct
15 Correct 34 ms 20984 KB Output is correct
16 Correct 32 ms 20984 KB Output is correct
17 Correct 34 ms 20352 KB Output is correct
18 Correct 36 ms 20216 KB Output is correct
19 Correct 29 ms 20216 KB Output is correct
20 Correct 32 ms 20216 KB Output is correct