oj.uz

Submission #95778

# Submission time Handle Problem Language Result Execution time Memory
95778 2019-02-02T14:27:04 Z JustInCase Uzastopni (COCI15_uzastopni) C++17
136 / 160
 86 ms 33792 KB 
#include <bits/stdc++.h>

const int32_t MAX_N = 10000;
const int32_t MAX_K = 100;

class Tree {
private:
	struct Node {
		bool isVisited;
		int32_t id, joke;
		std::vector< Node* > v;
		std::vector< std::pair< int32_t, int32_t > > dp;
	};

public:
	int32_t cntNodes;
	Node nodes[MAX_N + 5];

	void Init(int32_t pCntNodes = 0) {
		cntNodes = pCntNodes;
		for(int32_t i = 1; i <= cntNodes; i++) {
			nodes[i].id = i;
		}
	}

	void AddEdge(Node *x, Node *y) {
		x->v.push_back(y);
		y->v.push_back(x);
	}

	void CalcDp(Node *nd) {
		nd->isVisited = true;
		
		std::bitset< MAX_K + 5 > intervals[MAX_K + 5];
		std::vector< int32_t > q[MAX_K + 5];
		for(auto &x : nd->v) {
			if(!x->isVisited) {
				CalcDp(x);

				for(auto &i : x->dp) {
					q[i.first].push_back(i.second);
				}
			}
		}

		for(int32_t i = MAX_K; i >= 1; i--) {
			if(i == nd->joke) {
				intervals[i] |= intervals[i + 1];
				intervals[i].set(i);
			}
			else {
				for(auto &x : q[i]) {
					if(x < nd->joke || i > nd->joke) {
						intervals[i] |= intervals[x + 1];
						intervals[i].set(x);
					}
				}
			}

			for(int32_t j = MAX_K; j >= i; j--) {
				if(intervals[i].test(j)) {
					if(nd->joke >= i && nd->joke <= j) {
						nd->dp.push_back({ i, j });
					}
				}
			}
		}
	}
};

Tree t;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n;
	std::cin >> n;
	
	t.Init(n);
	for(int32_t i = 1; i <= n; i++) {
		std::cin >> t.nodes[i].joke;
	}

	for(int32_t i = 0; i < n - 1; i++) {
		int32_t x, y;
		std::cin >> x >> y;
		t.AddEdge(&t.nodes[x], &t.nodes[y]);
	}

	t.CalcDp(&t.nodes[1]);

	std::cout << t.nodes[1].dp.size() << '\n';
}

Subtask #1
136.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1020 KB Output is correct
6 Correct 3 ms 1276 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 3 ms 1276 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 83 ms 1852 KB Output is correct
12 Correct 83 ms 1784 KB Output is correct
13 Correct 84 ms 1784 KB Output is correct
14 Runtime error 41 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 37 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 36 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 83 ms 1808 KB Output is correct
18 Correct 82 ms 1784 KB Output is correct
19 Correct 86 ms 4316 KB Output is correct
20 Correct 85 ms 4216 KB Output is correct