Submission #684596

#	Time	Username	Problem	Language	Result	Execution time	Memory
684596		GusterGoose27	Uzastopni (COCI15_uzastopni)	C++11	160 / 160	10 ms	1492 KiB

uzastopni

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e4;
const int MAXM = 100;
bitset<MAXM> dp[MAXN][MAXM];
int n;
int val[MAXN];
vector<int> edges[MAXN];

struct comp {
	bool operator()(int &a, int &b) {
		return pii(val[a], a) < pii(val[b], b);
	}
} comp;

void make_dp(int cur, int l = 0, int r = MAXM-1) {
	if (val[cur] < l || val[cur] > r) return;
	sort(edges[cur].begin(), edges[cur].end(), comp);
	int p = 0;
	for (; p < edges[cur].size() && val[edges[cur][p]] < val[cur]; p++) {
		int nxt = edges[cur][p];
		make_dp(nxt, l, val[cur]-1);
		for (int i = l; i < val[nxt]; i++) {
			for (int j = l; j < val[nxt]; j++) {
				if (dp[cur][i][j]) dp[cur][i] |= dp[nxt][j+1];
			}
		}
		for (int i = l; i <= val[nxt]; i++) dp[cur][i] |= dp[nxt][i];
	}
	for (int i = l; i < val[cur]; i++) {
		bool b = dp[cur][i][val[cur]-1];
		dp[cur][i].reset();
		if (b) dp[cur][i][val[cur]] = 1;
	}
	dp[cur][val[cur]][val[cur]] = 1;
	for (; p < edges[cur].size(); p++) {
		int nxt = edges[cur][p];
		if (val[nxt] == val[cur]) continue;
		make_dp(nxt, val[cur]+1, r);
		for (int i = l; i < val[nxt]; i++) {
			for (int j = val[cur]; j < val[nxt]; j++) {
				if (dp[cur][i][j]) dp[cur][i] |= dp[nxt][j+1];
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> val[i];
		val[i]--;
	}
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y;
		edges[x-1].push_back(y-1);
	}
	make_dp(0);
	int ans = 0;
	for (int i = 0; i < MAXM; i++) ans += dp[0][i].count();
	cout << ans << "\n";
}

Compilation message (stderr)

uzastopni.cpp: In function 'void make_dp(int, int, int)':
uzastopni.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (; p < edges[cur].size() && val[edges[cur][p]] < val[cur]; p++) {
      |         ~~^~~~~~~~~~~~~~~~~~~
uzastopni.cpp:40:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (; p < edges[cur].size(); p++) {
      |         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160