oj.uz

Submission #51945

# Submission time Handle Problem Language Result Execution time Memory
51945 2018-06-22T17:24:25 Z mareksom File Paths (BOI15_fil) C++17
66 / 100
 265 ms 20760 KB 
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

constexpr int nax = 3005;

int n, m, k, s;
int ojc[nax];
int skok[nax];
int gleb[nax];
vector<int> cykle[nax];
vector<int> glebokosci;

bool Ok(int w, int len) {
  if (gleb[w] + len == k) {
    return true;
  }
  if (n <= 500 and m <= 500) {
    const int cpw = w;
    const int cplen = len;
    len += gleb[w];
    const int reszta = k - len;
    assert(reszta > 0);
    while (true) {
      for (int c : cykle[w]) {
        if (reszta % c == 0) {
          return true;
        }
      }
      if (w == 0) break;
      w = ojc[w];
    }
    w = cpw;
    len = cplen;
  }
  while (true) {
    if (binary_search(glebokosci.begin(), glebokosci.end(), k - len - s)) {
      return true;
    }
    if (w == 0) break;
    len += skok[w];
    w = ojc[w];
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k >> s;
  k--; s++;
  glebokosci.push_back(0);
  cykle[0].push_back(s);
  for (int i = 1; i <= n; i++) {
    cin >> ojc[i] >> skok[i];
    skok[i]++;
    gleb[i] = skok[i] + gleb[ojc[i]];
    glebokosci.push_back(gleb[i]);
    int j = i;
    int dlugosc = s;
    while (true) {
      cykle[j].push_back(dlugosc);
      if (j == 0) break;
      dlugosc += skok[j];
      j = ojc[j];
    }
  }
  sort(glebokosci.begin(), glebokosci.end());
  glebokosci.resize(unique(glebokosci.begin(), glebokosci.end()) - glebokosci.begin());
  for (int i = 0; i <= n; i++) {
    sort(cykle[i].begin(), cykle[i].end());
    cykle[i].resize(unique(cykle[i].begin(), cykle[i].end()) - cykle[i].begin());
  }

  while (m--) {
    int w, len;
    cin >> w >> len;
    if (Ok(w, len)) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
  return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Correct 5 ms 628 KB Output is correct
4 Correct 65 ms 948 KB Output is correct
5 Correct 9 ms 948 KB Output is correct
6 Correct 4 ms 948 KB Output is correct
7 Correct 101 ms 1296 KB Output is correct
8 Correct 4 ms 1296 KB Output is correct
9 Correct 5 ms 1296 KB Output is correct
10 Correct 2 ms 1296 KB Output is correct
11 Correct 4 ms 1296 KB Output is correct
12 Correct 38 ms 1296 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1296 KB Output is correct
2 Correct 4 ms 1296 KB Output is correct
3 Correct 7 ms 1296 KB Output is correct
4 Correct 6 ms 1296 KB Output is correct
5 Correct 265 ms 20760 KB Output is correct
6 Correct 245 ms 20760 KB Output is correct
7 Correct 132 ms 20760 KB Output is correct
8 Correct 147 ms 20760 KB Output is correct
9 Correct 9 ms 20760 KB Output is correct
10 Correct 6 ms 20760 KB Output is correct
11 Correct 9 ms 20760 KB Output is correct
12 Correct 265 ms 20760 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Correct 5 ms 628 KB Output is correct
4 Correct 65 ms 948 KB Output is correct
5 Correct 9 ms 948 KB Output is correct
6 Correct 4 ms 948 KB Output is correct
7 Correct 101 ms 1296 KB Output is correct
8 Correct 4 ms 1296 KB Output is correct
9 Correct 5 ms 1296 KB Output is correct
10 Correct 2 ms 1296 KB Output is correct
11 Correct 4 ms 1296 KB Output is correct
12 Correct 38 ms 1296 KB Output is correct
13 Correct 5 ms 1296 KB Output is correct
14 Correct 4 ms 1296 KB Output is correct
15 Correct 7 ms 1296 KB Output is correct
16 Correct 6 ms 1296 KB Output is correct
17 Correct 265 ms 20760 KB Output is correct
18 Correct 245 ms 20760 KB Output is correct
19 Correct 132 ms 20760 KB Output is correct
20 Correct 147 ms 20760 KB Output is correct
21 Correct 9 ms 20760 KB Output is correct
22 Correct 6 ms 20760 KB Output is correct
23 Correct 9 ms 20760 KB Output is correct
24 Correct 265 ms 20760 KB Output is correct
25 Incorrect 7 ms 20760 KB Output isn't correct
26 Halted 0 ms 0 KB -