Submission #480489

#	Time	Username	Problem	Language	Result	Execution time	Memory
480489		pure_mem	Uzastopni (COCI15_uzastopni)	C++14	80 / 160	216 ms	13124 KiB

uzastopni

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")

#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long 
#define MP make_pair

using namespace std;

const int N = 1e4 + 1, M = 100;
const ll mod = 1e9 + 7;

int n, cl[N];
vector<int> g[N];
vector< pair<int, int> > ans[N]; 
bitset<M> dp[M];

void dfs(int v) {
	for(int to: g[v])
		dfs(to);
	for(int i = M - 1;i >= 0;i--)
		dp[i].reset();
	for(int to: g[v]) {
		for(pair<int, int> &nx: ans[to])
			dp[nx.X][nx.Y] = 1;
	}
	dp[cl[v]][cl[v]] = 1;

	for(int i = M - 1;i >= 0;i--) {
		for(int j = i;j + 1 < M;j++) {
			if(dp[i][j] || dp[i]._Find_next(j) != M)
				dp[i] |= dp[j + 1];
		}
		for(int j = i;j < M;j++) {
			if(i <= cl[v] && cl[v] <= j && dp[i][j]) ans[v].push_back(MP(i, j));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> cl[i], cl[i]--;
	for(int i = 1, x, y;i < n;i++) {
		cin >> x >> y;
		g[x].push_back(y);
	} 
	dfs(1);
	cout << ans[1].size();
	return 0;
}

• Subtask 1: 80 / 160