oj.uz

Submission #480482

# Submission time Handle Problem Language Result Execution time Memory
480482 2021-10-16T15:00:45 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
80 / 160
 135 ms 8400 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 = 1e4 + 1, 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[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--) {
		dp[i].reset();
		for(int j: q[i]) {
			if(j + 1 < M)
				dp[i] |= dp[j + 1];
			dp[i][j] = 1;
		}
		for(int j = i;j < M;j++) {
			if(i <= cl[v] && cl[v] <= j && dp[i][j]) ans[v].push_back(MP(i, j));
			if(dp[i][j]) dp[j] |= dp[i];
		}
	}
}

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 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Incorrect 2 ms 972 KB Output isn't correct
4 Incorrect 2 ms 972 KB Output isn't correct
5 Incorrect 2 ms 972 KB Output isn't correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Incorrect 78 ms 1520 KB Output isn't correct
12 Incorrect 102 ms 1572 KB Output isn't correct
13 Correct 87 ms 1464 KB Output is correct
14 Incorrect 117 ms 8292 KB Output isn't correct
15 Incorrect 135 ms 8400 KB Output isn't correct
16 Incorrect 122 ms 8332 KB Output isn't correct
17 Correct 76 ms 1492 KB Output is correct
18 Correct 74 ms 1540 KB Output is correct
19 Incorrect 124 ms 3844 KB Output isn't correct
20 Incorrect 108 ms 3812 KB Output isn't correct