Submission #95781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95781	2019-02-02T14:33:52 Z	JustInCase	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	112 ms	23932 KB

uzastopni

#include <bits/stdc++.h>

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

std::vector< int32_t > q[MAX_K + 5];

class Tree {
private:
	struct Node {
		bool isVisited;
		int32_t id, joke;
		std::vector< Node* > v;
		std::vector< std::pair< int32_t, int32_t > > dp;
		std::bitset< MAX_K + 5 > intervals[MAX_K + 5];
	};

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;
		
		Node *par = nullptr;
		for(auto &x : nd->v) {
			if(!x->isVisited) {
				CalcDp(x);
			}
			else {
				par = x;
			}
		}

		for(int32_t i = 1; i <= MAX_K; i++) {
			q[i].clear();
		}
		
		for(auto &x : nd->v) {
			if(x != par) {
				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) {
				nd->intervals[i] |= nd->intervals[i + 1];
				nd->intervals[i].set(i);
			}
			else {
				for(auto &x : q[i]) {
					if(x < nd->joke || i > nd->joke) {
						nd->intervals[i] |= nd->intervals[x + 1];
						nd->intervals[i].set(x);
					}
				}
			}

			for(int32_t j = MAX_K; j >= i; j--) {
				if(nd->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

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	17404 KB	Output is correct
2	Correct	17 ms	17404 KB	Output is correct
3	Correct	16 ms	17400 KB	Output is correct
4	Correct	16 ms	17400 KB	Output is correct
5	Correct	16 ms	17400 KB	Output is correct
6	Correct	16 ms	17400 KB	Output is correct
7	Correct	17 ms	17528 KB	Output is correct
8	Correct	17 ms	17528 KB	Output is correct
9	Correct	18 ms	17400 KB	Output is correct
10	Correct	15 ms	17400 KB	Output is correct
11	Correct	102 ms	18144 KB	Output is correct
12	Correct	103 ms	18168 KB	Output is correct
13	Correct	112 ms	18168 KB	Output is correct
14	Correct	110 ms	23928 KB	Output is correct
15	Correct	104 ms	23892 KB	Output is correct
16	Correct	109 ms	23932 KB	Output is correct
17	Correct	92 ms	18168 KB	Output is correct
18	Correct	92 ms	18088 KB	Output is correct
19	Correct	95 ms	20600 KB	Output is correct
20	Correct	93 ms	20600 KB	Output is correct