Submission #713985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713985	2023-03-23T12:11:36 Z	Alex_tz307	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	24 ms	8620 KB

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.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	1 ms	724 KB	Output is correct
3	Correct	1 ms	796 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	14 ms	1336 KB	Output is correct
12	Correct	12 ms	1364 KB	Output is correct
13	Correct	13 ms	1440 KB	Output is correct
14	Correct	24 ms	8528 KB	Output is correct
15	Correct	24 ms	8620 KB	Output is correct
16	Correct	23 ms	8568 KB	Output is correct
17	Correct	14 ms	1360 KB	Output is correct
18	Correct	13 ms	1400 KB	Output is correct
19	Correct	13 ms	3680 KB	Output is correct
20	Correct	13 ms	3668 KB	Output is correct