oj.uz

답안 #874956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874956 2023-11-18T09:44:10 Z serifefedartar Uzastopni (COCI15_uzastopni) C++17
136 / 160
 93 ms 48372 KB 
#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.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 704 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 72 ms 17844 KB Output is correct
12 Correct 71 ms 17920 KB Output is correct
13 Correct 71 ms 17996 KB Output is correct
14 Runtime error 92 ms 48212 KB Memory limit exceeded
15 Runtime error 93 ms 48312 KB Memory limit exceeded
16 Runtime error 93 ms 48372 KB Memory limit exceeded
17 Correct 70 ms 17912 KB Output is correct
18 Correct 77 ms 18004 KB Output is correct
19 Correct 73 ms 20320 KB Output is correct
20 Correct 72 ms 20308 KB Output is correct