oj.uz

Submission #480489

# Submission time Handle Problem Language Result Execution time Memory
480489 2021-10-16T15:22:55 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
80 / 160
 216 ms 13124 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];
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--)
		dp[i].reset();
	for(int to: g[v]) {
		for(pair<int, int> &nx: ans[to])
			dp[nx.X][nx.Y] = 1;
	}
	dp[cl[v]][cl[v]] = 1;

	for(int i = M - 1;i >= 0;i--) {
		for(int j = i;j + 1 < M;j++) {
			if(dp[i][j] || dp[i]._Find_next(j) != M)
				dp[i] |= dp[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));
		}
	}
}

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 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Incorrect 2 ms 716 KB Output isn't correct
4 Incorrect 2 ms 716 KB Output isn't correct
5 Incorrect 2 ms 716 KB Output isn't correct
6 Correct 3 ms 800 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 796 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Incorrect 171 ms 1208 KB Output isn't correct
12 Incorrect 170 ms 1220 KB Output isn't correct
13 Correct 172 ms 1296 KB Output is correct
14 Incorrect 197 ms 12916 KB Output isn't correct
15 Incorrect 199 ms 13004 KB Output isn't correct
16 Incorrect 216 ms 13124 KB Output isn't correct
17 Correct 170 ms 1220 KB Output is correct
18 Correct 170 ms 1220 KB Output is correct
19 Incorrect 189 ms 3708 KB Output isn't correct
20 Incorrect 183 ms 3600 KB Output isn't correct