#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;
const ll mxN=3005;
vll adj[mxN];
ll dis[mxN];
ll lef[mxN];
ll rig[mxN];
ll p[2*mxN];
ll l[2*mxN];
vll mul[mxN]; //144
vll add[mxN]; // 144
bool ans[2*mxN]; // 16
ll cnt[1000005]; //16
ll cnt2[1000005]; //16
ll timer=0;
ll n, m, k, s;
void builddis(ll cur, ll d){
if(cur>n) return;
dis[cur]=d;
lef[cur]=timer;
timer++;
for(auto &chd:adj[cur]){
builddis(chd, d+l[chd]+1);
}
rig[cur]=timer;
}
bool under(ll a, ll b){
return lef[a]>=lef[b] && rig[a]<=rig[b];
}
void addedge(ll a, ll b){
if(under(a, b)){
mul[b].pb(dis[a]-dis[b]+s+1);
}
else{
ll newdis=dis[a]+s+1;
ll dif=newdis-dis[b];
if(dif>0){
add[b].pb(dif);
}
}
}
void dfs(ll cur, ll d){
if(cur>n){
ll need=k-d;
if(need==0){
ans[cur]=1;
return;
}
if(cnt[need]){
ans[cur]=1;
return;
}
for(ll i=1;i*i<=need;i++){
if(need%i==0){
if(cnt2[i] || cnt2[need/i]){
ans[cur]=1;
return;
}
}
}
ans[cur]=0;
return;
}
for(auto &it:add[cur]){
if(it<1000005) cnt[it]++;
}
for(auto &it:mul[cur]){
if(it<1000005) cnt2[it]++;
}
for(auto &chd:adj[cur]){
dfs(chd, d+l[chd]+1);
}
for(auto &it:add[cur]){
if(it<1000005) cnt[it]--;
}
for(auto &it:mul[cur]){
if(it<1000005) cnt2[it]--;
}
}
void solve(){
memset(dis, -1, sizeof(dis));
cin>>n>>m>>k>>s;
l[0]=0;
for(ll i=1;i<=n;i++){
cin>>p[i]>>l[i];
adj[p[i]].pb(i);
}
for(ll i=n+1;i<=n+m;i++){
cin>>p[i]>>l[i];
adj[p[i]].pb(i);
}
builddis(0, 0);
for(ll i=0;i<=n;i++){
for(ll j=0;j<=n;j++){
addedge(i, j);
}
}
dfs(0, 0);
for(ll i=n+1;i<=n+m;i++){
if(ans[i]){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
3164 KB |
Output is correct |
3 |
Correct |
4 ms |
7772 KB |
Output is correct |
4 |
Correct |
3 ms |
7516 KB |
Output is correct |
5 |
Correct |
5 ms |
9308 KB |
Output is correct |
6 |
Correct |
6 ms |
9304 KB |
Output is correct |
7 |
Correct |
5 ms |
9320 KB |
Output is correct |
8 |
Correct |
5 ms |
9052 KB |
Output is correct |
9 |
Correct |
5 ms |
9052 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
3252 KB |
Output is correct |
12 |
Correct |
2 ms |
3416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
37968 KB |
Output is correct |
2 |
Correct |
107 ms |
39408 KB |
Output is correct |
3 |
Correct |
102 ms |
35408 KB |
Output is correct |
4 |
Correct |
111 ms |
36828 KB |
Output is correct |
5 |
Correct |
84 ms |
41044 KB |
Output is correct |
6 |
Correct |
78 ms |
34388 KB |
Output is correct |
7 |
Correct |
109 ms |
42888 KB |
Output is correct |
8 |
Correct |
91 ms |
37080 KB |
Output is correct |
9 |
Correct |
117 ms |
45648 KB |
Output is correct |
10 |
Correct |
129 ms |
57956 KB |
Output is correct |
11 |
Correct |
63 ms |
24464 KB |
Output is correct |
12 |
Correct |
53 ms |
22352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
2 ms |
3164 KB |
Output is correct |
3 |
Correct |
4 ms |
7772 KB |
Output is correct |
4 |
Correct |
3 ms |
7516 KB |
Output is correct |
5 |
Correct |
5 ms |
9308 KB |
Output is correct |
6 |
Correct |
6 ms |
9304 KB |
Output is correct |
7 |
Correct |
5 ms |
9320 KB |
Output is correct |
8 |
Correct |
5 ms |
9052 KB |
Output is correct |
9 |
Correct |
5 ms |
9052 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
3252 KB |
Output is correct |
12 |
Correct |
2 ms |
3416 KB |
Output is correct |
13 |
Correct |
112 ms |
37968 KB |
Output is correct |
14 |
Correct |
107 ms |
39408 KB |
Output is correct |
15 |
Correct |
102 ms |
35408 KB |
Output is correct |
16 |
Correct |
111 ms |
36828 KB |
Output is correct |
17 |
Correct |
84 ms |
41044 KB |
Output is correct |
18 |
Correct |
78 ms |
34388 KB |
Output is correct |
19 |
Correct |
109 ms |
42888 KB |
Output is correct |
20 |
Correct |
91 ms |
37080 KB |
Output is correct |
21 |
Correct |
117 ms |
45648 KB |
Output is correct |
22 |
Correct |
129 ms |
57956 KB |
Output is correct |
23 |
Correct |
63 ms |
24464 KB |
Output is correct |
24 |
Correct |
53 ms |
22352 KB |
Output is correct |
25 |
Correct |
125 ms |
41596 KB |
Output is correct |
26 |
Correct |
110 ms |
39580 KB |
Output is correct |
27 |
Correct |
108 ms |
39056 KB |
Output is correct |
28 |
Correct |
102 ms |
35916 KB |
Output is correct |
29 |
Correct |
75 ms |
35172 KB |
Output is correct |
30 |
Correct |
90 ms |
40284 KB |
Output is correct |
31 |
Correct |
100 ms |
41552 KB |
Output is correct |
32 |
Correct |
108 ms |
42168 KB |
Output is correct |
33 |
Correct |
123 ms |
53412 KB |
Output is correct |
34 |
Correct |
139 ms |
58248 KB |
Output is correct |
35 |
Correct |
66 ms |
27408 KB |
Output is correct |
36 |
Correct |
63 ms |
27340 KB |
Output is correct |