oj.uz

Submission #199311

# Submission time Handle Problem Language Result Execution time Memory
199311 2020-01-31T00:32:29 Z MetB Uzastopni (COCI15_uzastopni) C++14
160 / 160
 123 ms 32248 KB 
#include <bits/stdc++.h>
 
#define N 1000001
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

vector <int> g[10000];

bitset <101> d[10000][100];
int vm = 101, v[10000], n;

void dfs (int x) {
	bitset <101> temp[101];
	int ptr = 0;
	for (int to : g[x]) {
		dfs (to);
		for (int i = 0; i < vm; i++) {
			temp[i] |= d[to][i];
		}
	}

	for (int i = vm - 1; i >= 0; i--) {
		for (int j = i + 1; j < vm; j++) {
			if (temp[i][j-1]) temp[i] |= temp[j];
		}
	}

	for (int i = 1; i <= v[x]; i++)
		for (int j = v[x]; j < vm; j++)
			if ((i == v[x] or temp[i][v[x] - 1]) and (j == v[x] or temp[v[x] + 1][j])) 
				d[x][i][j] = 1;
}

int main () {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		g[a-1].push_back (b - 1);
	}

	dfs (0);

	int ans = 0;

	for (int i = 0; i < vm; i++)
		ans += d[0][i].count ();

	cout << ans;
}

Compilation message

uzastopni.cpp: In function 'void dfs(int)':
uzastopni.cpp:18:6: warning: unused variable 'ptr' [-Wunused-variable]
  int ptr = 0;
      ^~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 888 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 100 ms 16376 KB Output is correct
12 Correct 101 ms 16380 KB Output is correct
13 Correct 95 ms 16376 KB Output is correct
14 Correct 121 ms 32248 KB Output is correct
15 Correct 123 ms 32248 KB Output is correct
16 Correct 121 ms 32248 KB Output is correct
17 Correct 94 ms 16376 KB Output is correct
18 Correct 96 ms 16444 KB Output is correct
19 Correct 117 ms 16248 KB Output is correct
20 Correct 114 ms 16248 KB Output is correct