oj.uz

Submission #94008

# Submission time Handle Problem Language Result Execution time Memory
94008 2019-01-14T15:46:57 Z vamaddur Uzastopni (COCI15_uzastopni) C++14
160 / 160
 69 ms 25380 KB 
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <deque>
#include <string.h>
#include <sstream>
#include <bitset>
#include <math.h>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
template <class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class T>
using ordered_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, less_equal<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

#define PI atan2(0, -1)
#define epsilon 1e-9
#define INF 5000000000000000000
#define MOD 1000000007

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

int N, arr [10010];
vector<int> adjacency [10010], process [10010];
vector<pair<int, int>> ret [10010];
bitset<110> dp [10010][110];

void dfs(int curr){
	for(int nexty : adjacency[curr]) dfs(nexty);
	for(int i = 0; i < 100; i++) process[i] = vector<int>();
	for(int nexty : adjacency[curr])
		for(pair<int, int> lol : ret[nexty])
			process[lol.f].pb(lol.s);
	for(int lo = 99; lo > -1; lo--){
		if(lo == arr[curr]){
			dp[curr][lo] |= dp[curr][lo+1];
			dp[curr][lo].set(lo);
		}
		else{
			for(int hi : process[lo]){
				if(lo <= arr[curr] && hi >= arr[curr]) continue;
				dp[curr][lo] |= dp[curr][hi+1];
				dp[curr][lo].set(hi);
			}	
		}
		if(arr[curr] >= lo)
			for(int hi = 99; hi >= arr[curr]; hi--)
				if(dp[curr][lo].test(hi))
					ret[curr].pb(mp(lo, hi));
	}
}

int main(){
    //freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10);
	cin >> N;
	for(int i = 0; i < N; i++){ cin >> arr[i]; arr[i]--; }
	for(int i = 1; i < N; i++){
		int a, b; cin >> a >> b; a--; b--;
		adjacency[a].pb(b);
	}
	dfs(0); cout << ret[0].size() << '\n';
	return 0;
}

/******************************
Kateba ii dake no hanashi darou
Success is only a victory away
- No Game No Life Opening
******************************/

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 3 ms 1272 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1272 KB Output is correct
11 Correct 45 ms 18940 KB Output is correct
12 Correct 40 ms 18936 KB Output is correct
13 Correct 33 ms 18936 KB Output is correct
14 Correct 69 ms 25380 KB Output is correct
15 Correct 68 ms 25336 KB Output is correct
16 Correct 68 ms 25336 KB Output is correct
17 Correct 34 ms 18936 KB Output is correct
18 Correct 33 ms 18852 KB Output is correct
19 Correct 61 ms 21240 KB Output is correct
20 Correct 61 ms 21240 KB Output is correct