Submission #1171511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171511		akamizane	Uzastopni (COCI15_uzastopni)	C++20	160 / 160	76 ms	30436 KiB

uzastopni

#include<bits/stdc++.h>

using namespace std;

#define debug(...) 42


#define int long long
using ll = long long;

const int maxn = 1e4 + 10;
const int maxk = 1e2 + 5;

vector<pair<int,int>> s[maxn];
vector<int> ad[maxn];
int val[maxn];
vector<int> q[maxk];

bitset<maxk> f[maxn][maxk];

void dfs(int u){
  for (auto v : ad[u]) dfs(v);
  for (int i = 0; i < maxk; i++) q[i].clear();
  for (auto v : ad[u]){
    for (auto [a, b] : s[v]){
      q[a].push_back(b);
    }
  }
  for (int l = maxk - 1; l >= 1; l--){
    if (l == val[u]){
      f[u][l] |= f[u][l + 1];
      f[u][l][l] = 1;
    }
    else{
      for (auto h : q[l]){
        if (h < val[u] || l > val[u]) {
          f[u][l] |= f[u][h + 1];
          f[u][l][h] = 1;
        }
      }
    }
    for (int h = maxk - 1; h >= l; h--)
      if (f[u][l][h] && val[u] >= l && val[u] <= h) {
      s[u].emplace_back(l, h);
    }
  }
}

void solve(){
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> val[i];
  for (int i = 0; i < n - 1; i++){
    int u, v;
    cin >> u >> v;
    ad[u].push_back(v);
  }
  dfs(1); 
  cout << s[1].size();
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

• Subtask 1: 160 / 160