oj.uz

Submission #131123

# Submission time Handle Problem Language Result Execution time Memory
131123 2019-07-16T15:01:00 Z nikolapesic2802 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 112 ms 25336 KB 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <bitset>
#include <vector>

#define lo first
#define hi second

using namespace std;

using interval = pair<int, int>;

const int MAXN = 10010;
const int MAXK = 110;

int n, v[MAXN];
vector<int> e[MAXN];

vector<interval> s[MAXN];
vector<int> q[MAXK];
bitset<MAXK> flag[MAXN][MAXK];

void dfs(int x) {
  for (auto y : e[x]) 
    dfs(y);

  for (int i = 0; i < MAXK; ++i)
    q[i].clear();
  for (auto y : e[x]) {
    for (auto it : s[y])
      q[it.lo].push_back(it.hi);
  }
  
  for (int lo = MAXK - 1; lo >= 1; --lo) {
    if (lo == v[x]) {
      flag[x][lo] |= flag[x][lo + 1];
      flag[x][lo].set(lo);
    } else {
      for (auto hi : q[lo]) {
      	if (hi < v[x] || lo > v[x]) {
      	  flag[x][lo] |= flag[x][hi + 1];
      	  flag[x][lo].set(hi);
      	}
      }
    }

    for (int hi = MAXK - 1; hi >= lo; --hi)
      if (flag[x][lo].test(hi) && v[x] >= lo && v[x] <= hi) {
    	s[x].emplace_back(lo, hi);
      }
  }
}

void init(void) {
  scanf("%d",&n);
  for (int i = 0; i < n; ++i)
    scanf("%d",&v[i]);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    scanf("%d %d",&a,&b);
    --a;
    --b;
    e[a].push_back(b);
  }
}

void solve(void) {
  dfs(0);
  printf("%d\n",s[0].size());
}

int main(void) {
  init();
  solve();
  return 0;
}

Compilation message

uzastopni.cpp: In function 'void solve()':
uzastopni.cpp:70:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",s[0].size());
                 ~~~~~~~~~~~^
uzastopni.cpp: In function 'void init()':
uzastopni.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
uzastopni.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&v[i]);
     ~~~~~^~~~~~~~~~~~
uzastopni.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 892 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1020 KB Output is correct
11 Correct 99 ms 18588 KB Output is correct
12 Correct 98 ms 18524 KB Output is correct
13 Correct 102 ms 18580 KB Output is correct
14 Correct 111 ms 25336 KB Output is correct
15 Correct 112 ms 25336 KB Output is correct
16 Correct 111 ms 25336 KB Output is correct
17 Correct 98 ms 18524 KB Output is correct
18 Correct 98 ms 18524 KB Output is correct
19 Correct 112 ms 20856 KB Output is correct
20 Correct 97 ms 20856 KB Output is correct