oj.uz

Submission #199310

# Submission time Handle Problem Language Result Execution time Memory
199310 2020-01-31T00:30:02 Z MetB Uzastopni (COCI15_uzastopni) C++14
56 / 160
 15 ms 764 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) {
	int ptr = 0;

	for (int to : g[x]) {
		dfs (to);
		for (int i = 0; i < vm; i++) {
			d[x][i] |= d[to][i];
		}
	}

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

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

	for (int i = 0; i < vm; i++)
		for (int j = i; j < vm; j++)
			if (j < v[x] || v[x] < i) d[x][i][j] = 0;
}

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:17:6: warning: unused variable 'ptr' [-Wunused-variable]
  int ptr = 0;
      ^~~

Subtask #1
56.0 / 160.0

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