Submission #1174613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174613		akool168	Uzastopni (COCI15_uzastopni)	C++20	72 / 160	192 ms	131072 KiB

uzastopni

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e4 + 2;
ll dp[102][102] = {0};
ll c[N];
vector < ll > adj[N];
//	ll pd[102][102] = {0};
//	ll d_p[102][102] = {0};
void Go(ll node, ll par) {
	ll j, r, sz;
ll pd[102][102] = {0};
ll d_p[102][102] = {0};
	for (int i = 0; i <= 101; i ++) {
		for (int j = 0; j <= 101; j ++) {
			pd[i][j] = 0;
			d_p[i][j] = 0;
		}
	}
	for ( ll chi : adj[node]) {
		if ( chi == par) continue;
		Go(chi, node);
		if ( chi == node ) continue;
		for ( j= 1; j <= 100; j ++) {
			for ( r = j; r <= 100; r ++) {
				pd[j][r] =pd[j][r] +  dp[j][r];
			}
		}
	}
	ll p = c[node];
	for ( sz = 1; sz <= 100; sz ++) {
		for ( r = 1;  r< sz; r ++) {
			if ( p - sz < 1) continue;
			pd[p - sz][p -1] = pd[p - sz][p - 1] + (pd[p - r][p - 1] * pd[p - sz][p - r - 1]);
		}
	}
	for ( sz = 1; sz <= 100; sz ++) {
		for ( r = 1;  r< sz; r ++) {
			if ( p + sz > 100) continue;
			pd[p+ 1][p + sz] = pd[p + 1][p + sz] + (pd[p + 1][p + r] * pd[p + r + 1][p+ sz]);
		}
	}
	
	for ( j= p; j >= 1; j --) {
		for ( r = p; r <= 100; r ++) {
			if(  r== p && j == p) {
				d_p[j][r] = 1;
				continue;
			}
			if ( r == p) {
				d_p[j][r] = pd[j][p - 1];
				continue;
			}
			if ( j == p) {
				d_p[j][r] = pd[p + 1][r];
				continue;
			}
			
			d_p[j][r] =d_p[j][r] +  pd[j][p - 1] * pd[p + 1][r];
		}
	}
	for (int i = 1; i <= 100; i ++) {
		for (j = 1; j <= 100; j ++) dp[i][j] = d_p[i][j];
	}
}

int main() {
	ll n, m, r, x, y, i, j, ans, t;
	
	cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> c[i];
	}
	
	for (i = 1; i < n; i ++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}	
	
	Go(1, 1);
	ans = 0;
	for (i = 1; i<= 100; i ++){
		for (j = i; j <= 100; j ++) {
			ans += dp[i][j];
		}
	}
	cout << ans << endl;


}

• Subtask 1: 72 / 160