oj.uz

Submission #480485

# Submission time Handle Problem Language Result Execution time Memory
480485 2021-10-16T15:06:34 Z pure_mem Uzastopni (COCI15_uzastopni) C++14
80 / 160
 118 ms 8100 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));
			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 1 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 2 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 68 ms 1488 KB Output isn't correct
12 Incorrect 66 ms 1476 KB Output isn't correct
13 Correct 68 ms 1456 KB Output is correct
14 Incorrect 117 ms 8092 KB Output isn't correct
15 Incorrect 118 ms 8100 KB Output isn't correct
16 Incorrect 118 ms 7988 KB Output isn't correct
17 Correct 70 ms 1492 KB Output is correct
18 Correct 79 ms 1564 KB Output is correct
19 Incorrect 111 ms 4000 KB Output isn't correct
20 Incorrect 110 ms 3920 KB Output isn't correct