oj.uz

Submission #95775

# Submission time Handle Problem Language Result Execution time Memory
95775 2019-02-02T14:23:36 Z JustInCase Uzastopni (COCI15_uzastopni) C++17
80 / 160
 69 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]) {
					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
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Incorrect 3 ms 1016 KB Output isn't correct
4 Incorrect 3 ms 1144 KB Output isn't correct
5 Incorrect 3 ms 1016 KB Output isn't correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1260 KB Output is correct
8 Correct 3 ms 1272 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Incorrect 68 ms 1824 KB Output isn't correct
12 Incorrect 63 ms 1912 KB Output isn't correct
13 Correct 64 ms 1912 KB Output is correct
14 Runtime error 36 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 36 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 63 ms 1892 KB Output is correct
18 Correct 68 ms 1912 KB Output is correct
19 Incorrect 69 ms 4344 KB Output isn't correct
20 Incorrect 69 ms 4304 KB Output isn't correct