Submission #476901

#	Time	Username	Problem	Language	Result	Execution time	Memory
476901		ntabc05101	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	152 ms	24644 KiB

uzastopni

#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 (stderr)

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