oj.uz

Submission #405532

# Submission time Handle Problem Language Result Execution time Memory
405532 2021-05-16T14:06:49 Z codebuster_10 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 467 ms 8132 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 

const int MAX_N = 10000, MAX_V = 105; 
bitset<MAX_V> dp[2][MAX_V], EMPTY;
vector<pair<int,int>> P[MAX_N];

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<int> v(n); 
  for(auto& i : v) cin >> i, --i;
  vector<int> g[n];
  for(int i = 0; i < n-1; ++i){
  	int a,b; cin >> a >> b; --a,--b;
  	g[a].push_back(b);
  }
  function<void(int)> dfs = [&](int i){
  	for(auto j : g[i])	dfs(j);
  	for(int j = 0; j < MAX_V; ++j) dp[0][j] = dp[1][j] = EMPTY;
  	for(auto j : g[i]){
  		for(auto [L,R] : P[j]){
  			if(R <= v[i] || v[i] < L){
  				dp[0][L][R] = true;
  				dp[1][R][L] = true;
  			}
  		}
  	}
  	dp[0][v[i]][v[i]+1] = true;
  	P[i].push_back({v[i],v[i]+1});
		dp[1][v[i]+1][v[i]] = true;
  	for(int len = 1; len < MAX_V; ++len){
  		for(int L = 0; L + len < MAX_V; ++L){
  			int R = L + len;
  			if(int((dp[0][L]&dp[1][R]).count())){
  				dp[0][L][R] = true;
  				if(dp[0][L][R] && L <= v[i] && v[i] < R){
  					P[i].push_back({L,R});
  				}
  				dp[1][R][L] = true;
  			}
  		}
  	}
  	return;
  };
  dfs(0);
  cout << int(P[0].size());
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 403 ms 1260 KB Output is correct
12 Correct 402 ms 1256 KB Output is correct
13 Correct 435 ms 1304 KB Output is correct
14 Correct 423 ms 7964 KB Output is correct
15 Correct 466 ms 7956 KB Output is correct
16 Correct 430 ms 8132 KB Output is correct
17 Correct 403 ms 1248 KB Output is correct
18 Correct 416 ms 1312 KB Output is correct
19 Correct 467 ms 3464 KB Output is correct
20 Correct 415 ms 3560 KB Output is correct