oj.uz

Submission #480487

# Submission time Handle Problem Language Result Execution time Memory
480487 2021-10-16T15:11:06 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
80 / 160
 125 ms 13028 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[M];
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]) {
			dp[i] |= dp[min(j + 1, M - 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));
			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 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Incorrect 2 ms 804 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 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Incorrect 70 ms 1208 KB Output isn't correct
12 Incorrect 73 ms 1256 KB Output isn't correct
13 Correct 93 ms 1288 KB Output is correct
14 Incorrect 120 ms 13028 KB Output isn't correct
15 Incorrect 117 ms 12920 KB Output isn't correct
16 Incorrect 125 ms 13008 KB Output isn't correct
17 Correct 65 ms 1280 KB Output is correct
18 Correct 66 ms 1220 KB Output is correct
19 Incorrect 99 ms 3680 KB Output isn't correct
20 Incorrect 108 ms 3632 KB Output isn't correct