Submission #405532

#	Time	Username	Problem	Language	Result	Execution time	Memory
405532		codebuster_10	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	467 ms	8132 KiB

uzastopni

#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 / 160