oj.uz

Submission #199309

# Submission time Handle Problem Language Result Execution time Memory
199309 2020-01-31T00:22:57 Z MetB Uzastopni (COCI15_uzastopni) C++14
80 / 160
 15 ms 920 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[100], gb[100];

bitset <101> d[100][100];
int vm = 101, v[100], 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
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 7 ms 496 KB Output is correct
11 Runtime error 9 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 9 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 10 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 10 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 10 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 10 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 9 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 9 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 15 ms 920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 15 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)