oj.uz

Submission #94361

# Submission time Handle Problem Language Result Execution time Memory
94361 2019-01-18T01:33:23 Z jasony123123 Uzastopni (COCI15_uzastopni) C++11
104 / 160
 154 ms 14200 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/**************************COCI15 R1 P6 uzastopni************************************/
const int SZ = 10000;
typedef array<bitset<100>, 100> dpt;
int N, J[SZ];
v<int> adj[SZ];
v<pii> dp[SZ];

dpt t, cd;
void dfs(int x, int p) {
	FOR(i, 0, 100) t[i].reset(), cd[i].reset();
	for (auto c : adj[x]) if (c != p)
		dfs(c, x);
	
	for (auto c : adj[x]) if (c != p)
		for (auto s : dp[c]) 
			t[s.first][s.second] = 1;

	RFORE(l, 99, J[x] + 1) {
		cd[l] = t[l];
		FORE(r, l, 99) if (t[l][r] && r + 1 <= 99) {
			cd[l] |= cd[r + 1];
		}
	}
	cd[J[x]][J[x]] = 1;
	if (J[x] != 99)
		cd[J[x]] |= cd[J[x] + 1];
	RFORE(l, J[x] - 1, 0) {
		FORE(r, l, J[x] - 1) if (t[l][r]) {
			cd[l][r] = 1;
			cd[l] |= cd[r + 1];
		}
	}
	FOR(l, 0, 100) FOR(r, l, 100) if (cd[l][r] && l<=J[x] && J[x]<=r)
		dp[x].push_back({ l,r });
}

int main() {
	io();
	cin >> N;
	FOR(i, 0, N) {
		cin >> J[i];
		J[i]--;
	}
	FOR(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		adj[a - 1].push_back(b - 1), adj[b - 1].push_back(a - 1);
	}
	dfs(0, -1);
	cout << dp[0].size() << "\n";
}

Subtask #1
104.0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 888 KB Output isn't correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Incorrect 3 ms 760 KB Output isn't correct
5 Incorrect 3 ms 888 KB Output isn't correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 129 ms 1500 KB Output is correct
12 Incorrect 133 ms 1628 KB Output isn't correct
13 Correct 136 ms 1528 KB Output is correct
14 Correct 154 ms 14200 KB Output is correct
15 Incorrect 152 ms 13432 KB Output isn't correct
16 Correct 151 ms 13048 KB Output is correct
17 Correct 135 ms 1500 KB Output is correct
18 Correct 136 ms 1500 KB Output is correct
19 Incorrect 118 ms 4112 KB Output isn't correct
20 Incorrect 117 ms 4032 KB Output isn't correct