oj.uz

Submission #23195

# Submission time Handle Problem Language Result Execution time Memory
23195 2017-05-04T11:49:07 Z model_code Uzastopni (COCI15_uzastopni) C++11
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 19736 KB Output is correct
2 Correct 0 ms 19736 KB Output is correct
3 Correct 0 ms 19736 KB Output is correct
4 Correct 0 ms 19736 KB Output is correct
5 Correct 0 ms 19736 KB Output is correct
6 Correct 0 ms 19736 KB Output is correct
7 Correct 0 ms 19736 KB Output is correct
8 Correct 0 ms 19736 KB Output is correct
9 Correct 0 ms 19736 KB Output is correct
10 Correct 0 ms 19736 KB Output is correct
11 Correct 196 ms 20264 KB Output is correct
12 Correct 213 ms 20264 KB Output is correct
13 Correct 196 ms 20264 KB Output is correct
14 Correct 193 ms 26292 KB Output is correct
15 Correct 193 ms 26292 KB Output is correct
16 Correct 203 ms 26292 KB Output is correct
17 Correct 229 ms 20264 KB Output is correct
18 Correct 189 ms 20264 KB Output is correct
19 Correct 169 ms 23408 KB Output is correct
20 Correct 186 ms 23400 KB Output is correct