oj.uz

Submission #476901

# Submission time Handle Problem Language Result Execution time Memory
476901 2021-09-29T02:23:00 Z ntabc05101 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 152 ms 24644 KB 
#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const int mxN = 10005;
const int mxK = 105;

int n, v[mxN + 1];
vector< array<int, 2> > s[mxN + 1];
vector<int> q[mxK + 1];
bitset<mxK + 1> f[mxN + 1][mxK + 1];
vector<int> adj[mxN + 1];

void dfs(int u) {
  for (auto &to: adj[u]) {
    dfs(to);
  }

  for (int i = 1; i <= mxK; i++) {
    q[i].clear();
  }
  for (auto &to: adj[u]) {
    for (auto &z: s[to]) {
      q[z[0]].push_back(z[1]);
    }
  }

  for (int lo = mxK; lo; lo--) {
    if (lo == v[u]) {
      f[u][lo] |= f[u][lo + 1];
      f[u][lo].set(lo);
    }
    else {
      for (auto &hi: q[lo]) {
        if (hi < v[u] || lo > v[u]) {
          f[u][lo] |= f[u][hi + 1];
          f[u][lo].set(hi);
        }
      }
    }
    for (int hi = mxK; hi; hi--) {
      if (f[u][lo].test(hi) && v[u] >= lo && v[u] <= hi) {
        s[u].push_back({lo, hi});
      }
    }
  }
}

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  else {
    if (fopen(taskname".in", "r")) {
      freopen(taskname".in", "r", stdin);
      freopen(taskname".out", "w", stdout);
    }
  }

  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (int i = 0, a, b; i < n - 1; i++) {
    cin >> a >> b; a--; b--;
    adj[a].push_back(b);
  }

  dfs(0);
  cout << s[0].size() << "\n";

  return 0;
}

Compilation message

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:57:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |       freopen(taskname".in", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:58:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |       freopen(taskname".out", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 928 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 2 ms 972 KB Output is correct
10 Correct 3 ms 972 KB Output is correct
11 Correct 120 ms 17980 KB Output is correct
12 Correct 152 ms 17952 KB Output is correct
13 Correct 147 ms 17984 KB Output is correct
14 Correct 142 ms 24540 KB Output is correct
15 Correct 133 ms 24644 KB Output is correct
16 Correct 135 ms 24536 KB Output is correct
17 Correct 134 ms 17976 KB Output is correct
18 Correct 133 ms 17952 KB Output is correct
19 Correct 126 ms 20448 KB Output is correct
20 Correct 122 ms 20344 KB Output is correct