Submission #1265461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265461		thuhienne	Uzastopni (COCI15_uzastopni)	C++20	160 / 160	25 ms	17480 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

int n,joke[10009],temp;
vector <int> adj[10009];

bitset <102> dp[10001][101];

void dfs(int node) {
	dp[node][joke[node]][joke[node]] = 1;
	temp = joke[node];
	sort(adj[node].begin(),adj[node].end(),[] (int a,int b) {
		return abs(joke[a] - temp) < abs(joke[b] - temp);
	});
	for (auto child : adj[node]) {
		dfs(child);
		//TH1: [x][node] (joke[x] < joke[node])
		if (joke[child] < joke[node]) {
			for (int left = 1;left <= joke[child];left++) {
				for (int right = joke[child];right < joke[node];right++) if (dp[child][left][right]) {
					dp[node][left] |= dp[node][right + 1];
				}
			}
		}
		//TH2: [node][x] (joke[node] < joke[x])
		if (joke[node] < joke[child]) {
			for (int left = joke[node];left >= 1;left--) {
				for (int right = joke[node];right <= 100;right++) if (dp[node][left][right]) {
					dp[node][left] |= dp[child][right + 1];
				}
			}
		}
	}
//	cout << "node: " << node << '\n';
//	for (int i = 1;i <= 6;i++) {
//		for (int j = 1;j <= 6;j++) {
//			cout << "[" << i << "," << j << "]" << ":" << dp[node][i][j] << '\n';
//		}
//	}
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> joke[i];
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
	}
	dfs(1);
	int res = 0;
	for (int i = 1;i <= 100;i++) res += dp[1][i].count();
	cout << res;
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 160 / 160