//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long ll;
#define int long long
const int N = 2e6+7;
vector<int> g[N], jad;
int dist[N], mos[N], dor[N], ans[N];
int n,m,k,s;
void dfs2(int r, int v, bool add){ // dor
if (v > n) return;
dor[dist[v]-dist[r]+s] += (add ? 1 : -1);
for(int u : g[v]) dfs2(r,u,add);
}
void dfs(int v){
if (v <= n){
jad.pb(v);
dfs2(v,v,1);
for(int u : g[v]) dfs(u);
dfs2(v,v,0);
jad.pop_back();
}
else{
// ziad
for(int par : jad){ // az koja mastaghim oomadim
int hav = dist[v] - dist[par] + s;
if (k-hav >= 0 && mos[k-hav]) ans[v-n] = 1;
}
// kam
int rem = k - dist[v];
for(int i=1; i*i <= rem; i++){
if (rem%i) continue;
if (dor[rem/i] || dor[rem/(rem/i)]) ans[v-n] = 1;
}
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> k >> s; s++;
dist[0] = 1;
mos[1] = 1;
for(int i=1; i<=n; i++){
int fa, megh; cin >> fa >> megh;
dist[i] = dist[fa] + megh + 1;
g[fa].pb(i);
mos[dist[i]] = 1;
}
for(int i=n+1; i<=n+m; i++){
int fa, megh; cin >> fa >> megh;
dist[i] = dist[fa] + megh;
if (dist[i] == k) ans[i-n] = 1;
g[fa].pb(i);
}
dfs(0);
for(int i=1; i<=m; i++) cout << (ans[i] ? "YES" : "NO") << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
54480 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
12 ms |
54364 KB |
Output is correct |
4 |
Correct |
16 ms |
54484 KB |
Output is correct |
5 |
Correct |
22 ms |
68700 KB |
Output is correct |
6 |
Correct |
15 ms |
66648 KB |
Output is correct |
7 |
Correct |
20 ms |
66836 KB |
Output is correct |
8 |
Correct |
15 ms |
68700 KB |
Output is correct |
9 |
Correct |
14 ms |
68700 KB |
Output is correct |
10 |
Correct |
13 ms |
54460 KB |
Output is correct |
11 |
Correct |
14 ms |
54364 KB |
Output is correct |
12 |
Correct |
18 ms |
54364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
69000 KB |
Output is correct |
2 |
Correct |
21 ms |
68956 KB |
Output is correct |
3 |
Correct |
21 ms |
69008 KB |
Output is correct |
4 |
Correct |
22 ms |
68952 KB |
Output is correct |
5 |
Correct |
138 ms |
69160 KB |
Output is correct |
6 |
Correct |
183 ms |
69228 KB |
Output is correct |
7 |
Correct |
88 ms |
68924 KB |
Output is correct |
8 |
Correct |
115 ms |
69112 KB |
Output is correct |
9 |
Correct |
25 ms |
66768 KB |
Output is correct |
10 |
Correct |
22 ms |
68860 KB |
Output is correct |
11 |
Correct |
15 ms |
54660 KB |
Output is correct |
12 |
Correct |
148 ms |
59176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
54480 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
12 ms |
54364 KB |
Output is correct |
4 |
Correct |
16 ms |
54484 KB |
Output is correct |
5 |
Correct |
22 ms |
68700 KB |
Output is correct |
6 |
Correct |
15 ms |
66648 KB |
Output is correct |
7 |
Correct |
20 ms |
66836 KB |
Output is correct |
8 |
Correct |
15 ms |
68700 KB |
Output is correct |
9 |
Correct |
14 ms |
68700 KB |
Output is correct |
10 |
Correct |
13 ms |
54460 KB |
Output is correct |
11 |
Correct |
14 ms |
54364 KB |
Output is correct |
12 |
Correct |
18 ms |
54364 KB |
Output is correct |
13 |
Correct |
21 ms |
69000 KB |
Output is correct |
14 |
Correct |
21 ms |
68956 KB |
Output is correct |
15 |
Correct |
21 ms |
69008 KB |
Output is correct |
16 |
Correct |
22 ms |
68952 KB |
Output is correct |
17 |
Correct |
138 ms |
69160 KB |
Output is correct |
18 |
Correct |
183 ms |
69228 KB |
Output is correct |
19 |
Correct |
88 ms |
68924 KB |
Output is correct |
20 |
Correct |
115 ms |
69112 KB |
Output is correct |
21 |
Correct |
25 ms |
66768 KB |
Output is correct |
22 |
Correct |
22 ms |
68860 KB |
Output is correct |
23 |
Correct |
15 ms |
54660 KB |
Output is correct |
24 |
Correct |
148 ms |
59176 KB |
Output is correct |
25 |
Correct |
20 ms |
68784 KB |
Output is correct |
26 |
Correct |
20 ms |
68956 KB |
Output is correct |
27 |
Correct |
20 ms |
69016 KB |
Output is correct |
28 |
Correct |
19 ms |
68880 KB |
Output is correct |
29 |
Correct |
135 ms |
69204 KB |
Output is correct |
30 |
Correct |
171 ms |
69228 KB |
Output is correct |
31 |
Correct |
110 ms |
69116 KB |
Output is correct |
32 |
Correct |
109 ms |
69120 KB |
Output is correct |
33 |
Correct |
20 ms |
68904 KB |
Output is correct |
34 |
Correct |
19 ms |
68872 KB |
Output is correct |
35 |
Correct |
15 ms |
54620 KB |
Output is correct |
36 |
Correct |
166 ms |
56848 KB |
Output is correct |