답안 #51946 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51946	2018-06-22T17:28:24 Z	mareksom	File Paths (BOI15_fil)	C++17	100 / 100	581 ms	25832 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); }

vector<int> Dzielniki(int n) {
  vector<int> d;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      d.push_back(i);
      d.push_back(n / i);
    }
  }
  sort(d.begin(), d.end());
  d.resize(unique(d.begin(), d.end()) - d.begin());
  return d;
}

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 (true or (n <= 500 and m <= 500)) {
    const int cpw = w;
    const int cplen = len;
    len += gleb[w];
    const int reszta = k - len;
    assert(reszta > 0);
    auto dzielniki = Dzielniki(reszta);
    while (true) {
      for (int d : dzielniki) {
        if (binary_search(cykle[w].begin(), cykle[w].end(), d)) {
          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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	13 ms	888 KB	Output is correct
5	Correct	9 ms	888 KB	Output is correct
6	Correct	5 ms	888 KB	Output is correct
7	Correct	21 ms	1184 KB	Output is correct
8	Correct	3 ms	1184 KB	Output is correct
9	Correct	4 ms	1184 KB	Output is correct
10	Correct	3 ms	1184 KB	Output is correct
11	Correct	3 ms	1184 KB	Output is correct
12	Correct	8 ms	1216 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	1216 KB	Output is correct
2	Correct	12 ms	1216 KB	Output is correct
3	Correct	11 ms	1216 KB	Output is correct
4	Correct	11 ms	1216 KB	Output is correct
5	Correct	581 ms	20756 KB	Output is correct
6	Correct	415 ms	20756 KB	Output is correct
7	Correct	396 ms	20756 KB	Output is correct
8	Correct	397 ms	20756 KB	Output is correct
9	Correct	18 ms	20756 KB	Output is correct
10	Correct	11 ms	20756 KB	Output is correct
11	Correct	20 ms	20756 KB	Output is correct
12	Correct	392 ms	20756 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	13 ms	888 KB	Output is correct
5	Correct	9 ms	888 KB	Output is correct
6	Correct	5 ms	888 KB	Output is correct
7	Correct	21 ms	1184 KB	Output is correct
8	Correct	3 ms	1184 KB	Output is correct
9	Correct	4 ms	1184 KB	Output is correct
10	Correct	3 ms	1184 KB	Output is correct
11	Correct	3 ms	1184 KB	Output is correct
12	Correct	8 ms	1216 KB	Output is correct
13	Correct	16 ms	1216 KB	Output is correct
14	Correct	12 ms	1216 KB	Output is correct
15	Correct	11 ms	1216 KB	Output is correct
16	Correct	11 ms	1216 KB	Output is correct
17	Correct	581 ms	20756 KB	Output is correct
18	Correct	415 ms	20756 KB	Output is correct
19	Correct	396 ms	20756 KB	Output is correct
20	Correct	397 ms	20756 KB	Output is correct
21	Correct	18 ms	20756 KB	Output is correct
22	Correct	11 ms	20756 KB	Output is correct
23	Correct	20 ms	20756 KB	Output is correct
24	Correct	392 ms	20756 KB	Output is correct
25	Correct	10 ms	20756 KB	Output is correct
26	Correct	10 ms	20756 KB	Output is correct
27	Correct	10 ms	20756 KB	Output is correct
28	Correct	11 ms	20756 KB	Output is correct
29	Correct	380 ms	20764 KB	Output is correct
30	Correct	424 ms	20920 KB	Output is correct
31	Correct	382 ms	20920 KB	Output is correct
32	Correct	303 ms	20920 KB	Output is correct
33	Correct	11 ms	20920 KB	Output is correct
34	Correct	9 ms	20920 KB	Output is correct
35	Correct	18 ms	20920 KB	Output is correct
36	Correct	545 ms	25832 KB	Output is correct

답안 #51946

Compilation message

Subtask #1 33.0 / 33.0

Subtask #2 33.0 / 33.0

Subtask #3 34.0 / 34.0

Subtask #1
33.0 / 33.0

Subtask #2
33.0 / 33.0

Subtask #3
34.0 / 34.0