Submission #39443

#	Time	Username	Problem	Language	Result	Execution time	Memory
39443		adamczh1	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	229 ms	26292 KiB

uzastopni

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

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