/*input
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int>dal[1000001];
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0), cerr.tie(0);
for (int i = 1; i <= 1000; i++)
for (int j = i * i; j <= 1000000; j += i)
dal[j].push_back(i);
int n, m, k, s;
cin >> n >> m >> k >> s;
s++;
int p[n + 1], d[n + 1], l[n + 1];
p[0] = -1;
d[0] = 1;
cc_hash_table<int, bool>D;
D.insert({1, true});
for (int i = 1; i <= n; i++)
{
cin >> p[i] >> l[i];
d[i] = d[p[i]] + 1 + l[i];
D[d[i]] = true;
}
cc_hash_table<int, bool>cikl;
for (int i = 0; i <= n; i++)
{
for (int j = i; j != -1; j = p[j])
{
cikl[j + (d[i] - d[j] + s) << 10] = true;
}
}
function<bool(int, int)>ok = [&](int v, int ilg)
{
if (d[v] == ilg)
return true;
if (ilg <= 0)
return false;
if (v != 0 && ok(p[v], ilg - 1 - l[v]))
return true;
if (D.find(ilg - s) != D.end())
return true;
if (ilg <= d[v] + s)
return false;
ilg -= d[v];
for (int c : dal[ilg])
{
if (cikl.find(v + (c << 10)) != cikl.end())
return true;
if (cikl.find(v + ((ilg / c) << 10)) != cikl.end())
return true;
}
return false;
};
while (m--)
{
int p, l;
cin >> p >> l;
if (ok(p, k - l))
cout << "YES\n";
else
cout << "NO\n";
}
}
Compilation message
fil.cpp: In function 'int main()':
fil.cpp:45:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
cikl[j + (d[i] - d[j] + s) << 10] = true;
~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
636 ms |
84632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
869 ms |
85112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
636 ms |
84632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
