Submission #928523

#	Time	Username	Problem	Language	Result	Execution time	Memory
928523		vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	77 ms	24756 KiB

uzastopni

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

#define N 10005
#define M 105
#define se second
#define fi first
#define ii pair<int, int>

int n, v[N];
vector<int> adj[N], rr[N];
vector<ii> cn[N];
bitset<M> gt[N][M];

bool in (int l, int r, int v){
	return (v >= l && v <= r);
}

void dfs(int u){
	for (auto x : adj[u]){
		dfs(x);
	}
	for (int i = 1; i <= 100; i++){
		rr[i].clear();
	}
	for (auto x : adj[u]){
		for (auto pi : cn[x]){
			int l = pi.fi;
			int r = pi.se;
			rr[l].push_back(r);
		}
	}
	for (int i = 100; i >= 1; i--){
		if (i == v[u]){
			gt[u][i] |= gt[u][i + 1];
			gt[u][i].set(i);
		}
		else {
			for (auto j : rr[i]){
				if (!in(i, j, v[u])){	
					gt[u][i] |= gt[u][j + 1];
					gt[u][i].set(j);
				}
			}
		}
		for (int j = 100; j >= i; j--){
			if (gt[u][i][j] && in(i, j, v[u])){
				cn[u].push_back({i, j});
			}
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> v[i];
	for (int i = 1; i <= n - 1; i++){
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}    

	dfs(1);

	cout << cn[1].size();

    return 0;
}     

• Subtask 1: 160 / 160