제출 #47716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47716		tieunhi	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	103 ms	24816 KiB

uzastopni

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define N 10005
#define PB push_back

using namespace std;

int n, a[N];
vector<pii> dp[N];
vector<int> g[N], v[101];
bitset<101> dd[N][101];

void DFS(int u, int p)
{
	for (auto ve : g[u])
	{
		if (ve == p) continue;
		DFS(ve, u);
	}
	for (int i = 1; i <= 100; i++)
		v[i].clear();
	for (auto ve : g[u])
		for (auto z : dp[ve])
			v[z.F].PB(z.S);

	for (int L = 100; L >= 1; L--)
	{
		if (L == a[u])
		{
			dd[u][L] |= dd[u][L+1];
			dd[u][L].set(L);
		}
		else
		{
			for (auto R : v[L])
				if (R < a[u] || L > a[u])
				{
					dd[u][L] |= dd[u][R+1];
					dd[u][L].set(R);
				}
		}
		for (int R = 100; R >= L; R--)
			if (dd[u][L].test(R) && L <= a[u] && R >= a[u])
				dp[u].PB({L, R});
	}
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("INP.TXT", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		g[u].PB(v);
		g[v].PB(u);
	}
	DFS(1, -1);
	cout <<dp[1].size();
}

• Subtask 1: 160 / 160