Submission #156334

#TimeUsernameProblemLanguageResultExecution timeMemory
156334amoo_safarFile Paths (BOI15_fil)C++14
66 / 100
1039 ms38276 KiB
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1e9 + 7;
const int Maxn = 3e3 + 10;
const ll Inf = 1000000000000000LL;

vector<pll> G[Maxn];
vector<pll> Q[Maxn];
vector<ll> R[Maxn];
bool ans[Maxn];
ll dep[Maxn];

map<ll, ll> mp;

void DFS(ll u, ll d = 0){
	dep[u] = d;
	R[u].pb(0);
	mp[d] = 1;
	for(auto E : G[u]){
		ll adj = E.F;
		DFS(adj, d + E.S);
		for(auto x : R[adj]) R[u].pb(x + E.S);
	}
	sort(all(R[u]));
	R[u].resize(unique(all(R[u])) - R[u].begin());
	R[u].shrink_to_fit();
}
ll SS;
ll cnt[1000010];
bool check(ll x){
	if(x < 0) return false;
	if(x == 0) return true;
	assert(x != 0);
	
	return (cnt[x] > 0);
}
ll n;
ll in[Maxn];
map<ll, ll> mp2;

void DFS2(ll u){
	for(auto x: R[u]) cnt[x] ++;
	in[u] = 1;
	for(auto E : G[u]){
		DFS2(E.F);
	}
	
		
	for(auto X : Q[u]){
		ll x = X.F - dep[u];
		mp2.clear();
		for(int i = 0; i <= n; i++){
			if(in[i] == 1) mp2[dep[u] - dep[i]] = 1;
		}
		for(int i = 0; i <= n; i++){
			if(mp2.count(X.F - dep[i] - SS - 1)) ans[X.S] = true;
		}
		//cerr << u << ' ' << X.F << ' ' << x << '\n';
		//if(x >= s + 1) ans[X.S] = (cnt[x - (s + 1)] > 0);
		for(int i = 1; i <= 1000; i++){
			if(x % i == 0){
				ans[X.S] |= check(i - (SS + 1));
				ans[X.S] |= check((x / i) - (SS + 1));
			}
		}
		if(x == 0) ans[X.S] = true;
	}
	in[u] = 0;
	for(auto x : R[u]) cnt[x] --;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll m, k;
	cin >> n >> m >> k >> SS;
	//assert(k > 10);
	ll p, l;
	for(int i = 1; i <= n; i++){
		cin >> p >> l;
		G[p].pb({i, l + 1});
	}
	for(int i = 1; i <= m; i++){
		cin >> p >> l;
		//assert(l < k-1);
		//assert(p != 0);
		//if(p == 0){
	//		ans[i] = (( (k - l - 1) % (s + 1) ) == 0);
	//	}
		Q[p].pb({k - l - 1, i});
	}
	//cerr << '\n';
	DFS(0);
	DFS2(0);
	
	for(int i = 1; i <= m; i++) cout << (ans[i] ? "YES\n" : "NO\n");
	
	return 0;
}

/*
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...