Submission #713985

#	Time	Username	Problem	Language	Result	Execution time	Memory
713985		Alex_tz307	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	24 ms	8620 KiB

uzastopni

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e4;
const int kK = 100;
int a[1 + kN];
vector<int> g[1 + kN], st[1 + kK], dr[1 + kK];
vector<pair<int, int>> intervals[1 + kN];
bitset<1 + kK + 1> reach;

void dfs(int u) {
  for (const int &v : g[u]) {
    dfs(v);
  }

  for (int i = 1; i <= kK; ++i) {
    st[i].clear();
    dr[i].clear();
  }

  for (const int &v : g[u]) {
    for (const auto &range : intervals[v]) {
      if (a[u] < range.first) {
        dr[range.second].emplace_back(range.first - 1);
      } else if (range.second < a[u]) {
        st[range.first].emplace_back(range.second + 1);
      }
    }

    intervals[v].clear();
  }

  reach.reset();

  reach.set(a[u]);

  vector<int> left;

  for (int l = kK; l > 0; --l) {
    if (!reach[l]) {
      for (const int &r : st[l]) {
        if (reach[r]) {
          reach.set(l);
          break;
        }
      }
    }

    if (reach[l]) {
      left.emplace_back(l);
    }
  }

  reach.reset();

  reach.set(a[u]);

  vector<int> right;

  for (int r = 1; r <= kK; ++r) {
    if (!reach[r]) {
      for (const int &l : dr[r]) {
        if (reach[l]) {
          reach.set(r);
          break;
        }
      }
    }

    if (reach[r]) {
      right.emplace_back(r);
    }
  }

  for (const int &l : left) {
    for (const int &r : right) {
      intervals[u].emplace_back(l, r);
    }
  }

  left.clear();
  right.clear();
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }

  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;

    g[u].emplace_back(v);
  }

  dfs(1);

  cout << intervals[1].size() << '\n';

  return 0;
}

• Subtask 1: 160 / 160