#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
const int MXN = 6005;
const int MXR = 1e6+5;
int n, m, k, s;
vi adj[MXN];
ll len[MXN], path[MXN];
bool path_present[MXR];
bool ans[MXN];
vi cycles[MXN];
int cycle_cnt[MXR];
vi up;
void init_cycles(int u, int p) {
if(u > n) return;
up.PB(u);
for(int v : up) {
cycles[v].PB(path[u]-path[v]+s);
}
for(int v : adj[u]) if(v != p) {
init_cycles(v, u);
}
up.pop_back();
}
void upd(int sum, int change) {
if(sum >= MXR) return;
cycle_cnt[sum] += change;
}
vi get_divs(int sum) {
vi divs;
for(int i = 1; i*i <= sum; i++) {
if(sum % i) continue;
divs.PB(i);
if(i != sum/i) divs.PB(sum/i);
}
return divs;
}
void dfs(int u, int p) {
up.PB(u);
if(u > n) {
ans[u] = path[u] == k;
for(int v : up) {
if(k-(path[u]-path[v]+len[v]+s) >= 0
&& path_present[k-(path[u]-path[v]+len[v]+s)])
ans[u] = true;
}
if(path[u] < k) {
vi divs = get_divs(k-path[u]);
for(int x : divs) {
if(cycle_cnt[x]) ans[u] = true;
}
}
up.pop_back();
return;
}
for(int sum : cycles[u]) upd(sum, 1);
for(int v : adj[u]) if(v != p) {
dfs(v, u);
}
up.pop_back();
for(int sum : cycles[u]) upd(sum, -1);
}
int main() {
cin >> n >> m >> k >> s; s++;
path_present[0] = true;
for(int i = 1; i <= n; i++) {
int p; cin >> p >> len[i]; len[i]++;
adj[p].PB(i);
path[i] += path[p]+len[i];
path_present[path[i]] = true;
}
for(int i = n+1; i <= n+m; i++) {
int p; cin >> p >> len[i]; len[i]++;
adj[p].PB(i);
path[i] += path[p]+len[i];
}
init_cycles(0, -1);
dfs(0, -1);
for(int i = n+1; i <= n+m; i++) cout << (ans[i] ? "YES\n" : "NO\n");
return 0;
}
/*
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
1108 KB |
Output is correct |
4 |
Correct |
3 ms |
1492 KB |
Output is correct |
5 |
Correct |
6 ms |
4812 KB |
Output is correct |
6 |
Correct |
5 ms |
3412 KB |
Output is correct |
7 |
Correct |
7 ms |
5332 KB |
Output is correct |
8 |
Correct |
4 ms |
4452 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
1372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
5532 KB |
Output is correct |
2 |
Correct |
13 ms |
5460 KB |
Output is correct |
3 |
Correct |
13 ms |
5708 KB |
Output is correct |
4 |
Correct |
14 ms |
5588 KB |
Output is correct |
5 |
Correct |
87 ms |
25412 KB |
Output is correct |
6 |
Correct |
87 ms |
25572 KB |
Output is correct |
7 |
Correct |
53 ms |
16076 KB |
Output is correct |
8 |
Correct |
56 ms |
16484 KB |
Output is correct |
9 |
Correct |
13 ms |
5204 KB |
Output is correct |
10 |
Correct |
13 ms |
4564 KB |
Output is correct |
11 |
Correct |
7 ms |
1480 KB |
Output is correct |
12 |
Correct |
73 ms |
22000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
2 ms |
1108 KB |
Output is correct |
4 |
Correct |
3 ms |
1492 KB |
Output is correct |
5 |
Correct |
6 ms |
4812 KB |
Output is correct |
6 |
Correct |
5 ms |
3412 KB |
Output is correct |
7 |
Correct |
7 ms |
5332 KB |
Output is correct |
8 |
Correct |
4 ms |
4452 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
1372 KB |
Output is correct |
13 |
Correct |
15 ms |
5532 KB |
Output is correct |
14 |
Correct |
13 ms |
5460 KB |
Output is correct |
15 |
Correct |
13 ms |
5708 KB |
Output is correct |
16 |
Correct |
14 ms |
5588 KB |
Output is correct |
17 |
Correct |
87 ms |
25412 KB |
Output is correct |
18 |
Correct |
87 ms |
25572 KB |
Output is correct |
19 |
Correct |
53 ms |
16076 KB |
Output is correct |
20 |
Correct |
56 ms |
16484 KB |
Output is correct |
21 |
Correct |
13 ms |
5204 KB |
Output is correct |
22 |
Correct |
13 ms |
4564 KB |
Output is correct |
23 |
Correct |
7 ms |
1480 KB |
Output is correct |
24 |
Correct |
73 ms |
22000 KB |
Output is correct |
25 |
Correct |
14 ms |
5268 KB |
Output is correct |
26 |
Correct |
12 ms |
5440 KB |
Output is correct |
27 |
Correct |
12 ms |
5460 KB |
Output is correct |
28 |
Correct |
14 ms |
5588 KB |
Output is correct |
29 |
Correct |
84 ms |
25560 KB |
Output is correct |
30 |
Correct |
82 ms |
25480 KB |
Output is correct |
31 |
Correct |
54 ms |
16300 KB |
Output is correct |
32 |
Correct |
56 ms |
16056 KB |
Output is correct |
33 |
Correct |
10 ms |
4564 KB |
Output is correct |
34 |
Correct |
10 ms |
4648 KB |
Output is correct |
35 |
Correct |
7 ms |
1492 KB |
Output is correct |
36 |
Correct |
85 ms |
26096 KB |
Output is correct |