#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 6e3 + 5, maxk = 1e6 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int l[maxn], par[maxn], n, m, k, s;
vector<int> adj[maxn];
int vl[maxk], vl2[maxk];
bool ans[maxn];
vector<int> dv[maxk];
vector<int> res;
void dfs3(int r, int h = s){
if(r > n) return;
res.pb(h);
for(int c: adj[r]) dfs3(c, h + l[c]);
}
void dfs2(int r, int x, int h = 0){
if(r == x || r > n) return;
res.pb(h + s);
for(int c: adj[r]) dfs2(c, x, h + l[c]);
}
void add(int u, int h){
res.clear();
dfs3(u);
for(int c: res) vl[c]++;
res.clear();
dfs2(0, u);
for(ll c: res) if(c > h) vl2[c-h]++;
}
void del(int u, int h){
res.clear();
dfs3(u);
for(int c: res) vl[c]--;
res.clear();
dfs2(0, u);
for(ll c: res) if(c > h) vl2[c-h]--;
}
void dfs(int r, ll h = 0){
if(r > n){ r -= n;
ll t = k - h;
ans[r] = vl2[t] || t == 0;
if(!ans[r]){
for(int j = 1; j*j <= t; j++){
if(t%j == 0){
if(vl[j] || vl[t/j]){
ans[r] = true;
break;
}
}
}
}
}else{
add(r, h);
for(int c: adj[r]) dfs(c, h + l[c]);
del(r, h);
}
}
int main(){ IOS();
// rep(i,1,maxk) for(int j = i; j < maxk; j += i) dv[j].pb(i);
par[0] = -1;
cin >> n >> m >> k >> s; s++;
rep(i,1,n+m+1) cin >> par[i] >> l[i], adj[par[i]].pb(i), l[i]++;
dfs(0);
rep(i,1,m+1) cout << (ans[i]?"YES\n":"NO\n");
return 0;
}
Compilation message
fil.cpp: In function 'void IOS()':
fil.cpp:19:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fil.cpp:20:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen("out.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
24028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
