oj.uz

Submission #39443

# Submission time Handle Problem Language Result Execution time Memory
39443 2018-01-15T07:51:38 Z adamczh1 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 229 ms 26292 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:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
uzastopni.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&v[i]);
                      ^
uzastopni.cpp:61:25: 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 0 ms 19732 KB Output is correct
2 Correct 0 ms 19732 KB Output is correct
3 Correct 0 ms 19732 KB Output is correct
4 Correct 0 ms 19732 KB Output is correct
5 Correct 0 ms 19732 KB Output is correct
6 Correct 3 ms 19732 KB Output is correct
7 Correct 0 ms 19732 KB Output is correct
8 Correct 3 ms 19732 KB Output is correct
9 Correct 3 ms 19732 KB Output is correct
10 Correct 0 ms 19732 KB Output is correct
11 Correct 219 ms 20260 KB Output is correct
12 Correct 213 ms 20260 KB Output is correct
13 Correct 223 ms 20260 KB Output is correct
14 Correct 209 ms 26292 KB Output is correct
15 Correct 199 ms 26284 KB Output is correct
16 Correct 216 ms 26284 KB Output is correct
17 Correct 226 ms 20260 KB Output is correct
18 Correct 226 ms 20260 KB Output is correct
19 Correct 199 ms 23404 KB Output is correct
20 Correct 229 ms 23396 KB Output is correct