oj.uz

Submission #480479

# Submission time Handle Problem Language Result Execution time Memory
480479 2021-10-16T14:48:09 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
80 / 160
 49 ms 23880 KB 
#pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")

#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long 
#define MP make_pair

using namespace std;

const int N = 10001, M = 100;
const ll mod = 1e9 + 7;

int n, cl[N];
vector<int> g[N], q[N];
vector< pair<int, int> > ans[N]; 
bitset<M> dp[N][M];

void dfs(int v) {
	for(int to: g[v])
		dfs(to);
	for(int i = M - 1;i >= 0;i--)
		q[i].clear();
	for(int to: g[v]) {
		for(pair<int, int> &nx: ans[to])
			q[nx.X].push_back(nx.Y);
	}
	q[cl[v]].push_back(cl[v]);
	for(int i = M - 1;i >= 0;i--) {
		for(int j: q[i]) {
			dp[v][i][j] = 1;
			if(j + 1 < M)
				dp[v][i] |= dp[v][j + 1];
		}
		if(i > cl[v]) continue;
		for(int j = cl[v];j < M;j++) {
			if(dp[v][i][j]) ans[v].push_back(MP(i, j));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> cl[i], cl[i]--;
	for(int i = 1, x, y;i < n;i++) {
		cin >> x >> y;
		g[x].push_back(y);
	} 
	dfs(1);
	cout << ans[1].size();
	return 0;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 1 ms 1100 KB Output isn't correct
4 Incorrect 1 ms 1100 KB Output isn't correct
5 Incorrect 1 ms 1148 KB Output isn't correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Incorrect 23 ms 17304 KB Output isn't correct
12 Incorrect 21 ms 17300 KB Output isn't correct
13 Correct 21 ms 17308 KB Output is correct
14 Incorrect 49 ms 23880 KB Output isn't correct
15 Incorrect 48 ms 23776 KB Output isn't correct
16 Incorrect 49 ms 23824 KB Output isn't correct
17 Correct 20 ms 17356 KB Output is correct
18 Correct 29 ms 17244 KB Output is correct
19 Incorrect 38 ms 19596 KB Output isn't correct
20 Incorrect 38 ms 19568 KB Output isn't correct