제출 #874956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874956		serifefedartar	Uzastopni (COCI15_uzastopni)	C++17	136 / 160	93 ms	48372 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 10007;
const ll LOGN = 20; 
const ll MAXN = 1e4 + 100;

vector<vector<int>> graph;
vector<pair<int,int>> possible[MAXN];
bitset<105> bs[MAXN][105];
int V[MAXN];

void dfs(int node) {
	for (auto u : graph[node])
		dfs(u);

	vector<int> border[105];
	for (auto u : graph[node]) {
		for (auto q : possible[u])
			border[q.f].push_back(q.s);
	}

	for (int i = 104; i >= 1; i--) {
		if (i == V[node]) {
			bs[node][i] |= bs[node][i+1];
			bs[node][i].set(i);
		} else {
			for (auto u : border[i]) {
				if (u < V[node] || i > V[node]) {
					bs[node][i] |= bs[node][u + 1];
					bs[node][i].set(u); 
				}
			}
		}

		for (int r = i; r <= 104; r++) {
			if (bs[node][i].test(r) && V[node] >= i && V[node] <= r)
				possible[node].push_back({i, r});
		}
	}
}

int main() {
	fast
	int N, A, B;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> V[i];

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> A >> B;
		graph[A].push_back(B);
	}
	dfs(1);
	cout << possible[1].size() << "\n";
}

• Subtask 1: 136 / 160