Submission #1143391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143391		THXuan	Uzastopni (COCI15_uzastopni)	C++20	160 / 160	38 ms	6472 KiB

uzastopni

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

const ll maxn = 10005, m = 105;
int v[maxn], dp[maxn][m];
vector<int>adj[maxn];
int now = 0;
bool comp(int x, int y) {
	return abs(v[x] - v[now]) < abs(v[y] - v[now]);
}

bool flag(int u, int lf, int rg) {
	if (v[u] < lf || v[u] > rg) return false;
	return dp[u][lf] && dp[u][rg];
}

void dfs(int s){
	dp[s][v[s]] = true;
	vector<int>a;
	for (auto u : adj[s]) {
		dfs(u);
		a.push_back(u);
	}
	now = s;
	sort(a.begin(), a.end(), comp);
	for (auto u : a) {
		for (int i = 1; i <= 100; i++) {
			for (int k = min(i, v[s]) + 1; k <= max(i, v[s]); k++) {
				if (i < v[s]) {
					if (dp[s][k] && flag(u, i, k - 1)) {
						dp[s][i] = true;
					}
				}
				else {
					if (dp[s][k - 1] && flag(u, k, i)) {
						dp[s][i] = true;
					}
				}
			}
		}
	}
}

void solve()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> v[i];
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
	}
	dfs(1);
	int lf = 1; int rg = 1;
	for (int i = 1; i < v[1]; i++)lf += dp[1][i];
	for (int i = v[1] + 1; i <= 100; i++)rg += dp[1][i];
	cout << (lf * rg) << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1; //cin>>t;
	while (t--) solve();
	return 0;
}

• Subtask 1: 160 / 160