Submission #95780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95780	2019-02-02T14:32:39 Z	JustInCase	Uzastopni (COCI15_uzastopni)	C++17	104 / 160	186 ms	31096 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;
		
		for(int32_t i = 1; i <= MAX_K; i++) {
			q[i].clear();
		}

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

104.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	17400 KB	Output isn't correct
2	Correct	14 ms	17388 KB	Output is correct
3	Correct	15 ms	17400 KB	Output is correct
4	Incorrect	14 ms	17400 KB	Output isn't correct
5	Incorrect	17 ms	17400 KB	Output isn't correct
6	Correct	15 ms	17400 KB	Output is correct
7	Correct	15 ms	17528 KB	Output is correct
8	Correct	14 ms	17528 KB	Output is correct
9	Correct	15 ms	17400 KB	Output is correct
10	Correct	17 ms	17400 KB	Output is correct
11	Correct	92 ms	18048 KB	Output is correct
12	Incorrect	99 ms	18040 KB	Output isn't correct
13	Correct	116 ms	18168 KB	Output is correct
14	Correct	167 ms	31096 KB	Output is correct
15	Incorrect	169 ms	30052 KB	Output isn't correct
16	Correct	186 ms	29944 KB	Output is correct
17	Correct	120 ms	18144 KB	Output is correct
18	Correct	102 ms	18184 KB	Output is correct
19	Incorrect	103 ms	20784 KB	Output isn't correct
20	Incorrect	121 ms	20600 KB	Output isn't correct