답안 #95780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95780 2019-02-02T14:32:39 Z JustInCase Uzastopni (COCI15_uzastopni) C++17
104 / 160
186 ms 31096 KB
#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';
}

# 결과 실행 시간 메모리 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