oj.uz

Submission #480488

# Submission time Handle Problem Language Result Execution time Memory
480488 2021-10-16T15:16:36 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
0 / 160
 175 ms 2140 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--) {
		dp[i].reset();
		for(int j = i;j < M;j++) {
			if(dp[i]._Find_next(j) != M)
				dp[i] |= dp[j];
		}
		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
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 716 KB Output isn't correct
2 Incorrect 2 ms 716 KB Output isn't correct
3 Incorrect 2 ms 716 KB Output isn't correct
4 Incorrect 2 ms 844 KB Output isn't correct
5 Incorrect 2 ms 716 KB Output isn't correct
6 Incorrect 2 ms 716 KB Output isn't correct
7 Incorrect 2 ms 716 KB Output isn't correct
8 Incorrect 2 ms 716 KB Output isn't correct
9 Incorrect 2 ms 716 KB Output isn't correct
10 Incorrect 2 ms 716 KB Output isn't correct
11 Incorrect 144 ms 972 KB Output isn't correct
12 Incorrect 173 ms 972 KB Output isn't correct
13 Incorrect 137 ms 968 KB Output isn't correct
14 Incorrect 164 ms 2140 KB Output isn't correct
15 Incorrect 155 ms 2124 KB Output isn't correct
16 Incorrect 175 ms 2072 KB Output isn't correct
17 Incorrect 145 ms 976 KB Output isn't correct
18 Incorrect 139 ms 972 KB Output isn't correct
19 Incorrect 159 ms 844 KB Output isn't correct
20 Incorrect 158 ms 860 KB Output isn't correct