Submission #480494

#	Time	Username	Problem	Language	Result	Execution time	Memory
480494		pure_mem	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	127 ms	7516 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], tmp;

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]].reset();
	for(int i = M - 1;i >= 0;i--) {
		if(i == cl[v]) {
			if(i + 1 < M) dp[i] = dp[i + 1];
			dp[i][i] = 1;
		}
		else {
			tmp.reset();
			for(int j = M - 1;j >= i;j--) {
				if(i <= cl[v] && cl[v] <= j) continue;
				if(dp[i][j]) {
					if(j + 1 < M) tmp |= dp[j + 1];
					tmp[j] = 1; 
				}
			}
			dp[i] = tmp;
		}
		if(i > cl[v]) continue;
		for(int j = cl[v];j < M;j++)
			if(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: 160 / 160