oj.uz

Submission #684596

# Submission time Handle Problem Language Result Execution time Memory
684596 2023-01-21T23:51:54 Z GusterGoose27 Uzastopni (COCI15_uzastopni) C++11
160 / 160
 10 ms 1492 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 548 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 1 ms 552 KB Output is correct
6 Correct 1 ms 548 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 7 ms 1492 KB Output is correct
12 Correct 6 ms 980 KB Output is correct
13 Correct 6 ms 964 KB Output is correct
14 Correct 10 ms 980 KB Output is correct
15 Correct 6 ms 944 KB Output is correct
16 Correct 7 ms 980 KB Output is correct
17 Correct 6 ms 952 KB Output is correct
18 Correct 7 ms 980 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 6 ms 820 KB Output is correct