#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(v) begin(v), end(v)
using ll = long long;
struct edge {
int to;
ll cost;
edge(int t, ll c) : to(t), cost(c) {}
};
int main() {
int n, m, k, s; cin >> n >> m >> k >> s;
++n;
vector<vector<edge>> g(n);
vector<int> par(n, -1);
++s;
rep2 (i, 1, n) {
int p, l; cin >> p >> l;
g[p].emplace_back(i, l + 1);
par[i] = p;
}
vector<ll> d(n);
vector<vector<ll>> ch(n);
{
auto dfs = [&](auto&& self, int v) -> vector<ll> {
vector<ll> res;
for (auto e : g[v]) {
d[e.to] = d[v] + e.cost;
for (auto i : self(self, e.to)) res.push_back(i + e.cost);
}
res.push_back(0);
return ch[v] = res;
};
dfs(dfs, 0);
}
vector<bool> exist(3 * k + 1, false);
rep (i, n) {
if (d[i] <= 3 * k) exist[d[i]] = true;
}
vector<vector<pair<int, int>>> qs(n);
vector<bool> ans(m, false);
rep (i, m) {
int p, l; cin >> p >> l;
int t = k - l - 1;
if (d[p] == t) ans[i] = true;
else {
t -= d[p];
if (t < s) continue;
qs[p].emplace_back(i, t);
for (int j = p; j != -1; j = par[j]) {
if (t + d[j] - s <= 3 * k && exist[t + d[j] - s]) ans[i] = true;
}
}
}
{
vector<int> cnt(k + 1);
auto dfs = [&](auto&& self, int v) -> void {
for (auto i : ch[v]) {
if (i <= k) ++cnt[i];
}
for (auto [i, t] : qs[v]) {
for (ll j = 1; j * j <= t; ++j) {
if (t % j != 0) continue;
if (s <= j && cnt[j - s] > 0) ans[i] = true;
if (s <= t / j && cnt[t / j - s] > 0) ans[i] = true;
}
}
for (auto e : g[v]) self(self, e.to);
for (auto i : ch[v]) {
if (i <= k) --cnt[i];
}
};
dfs(dfs, 0);
}
for (auto i : ans) puts(i ? "YES" : "NO");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
