oj.uz

답안 #156320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156320 2019-10-05T06:32:41 Z amoo_safar File Paths (BOI15_fil) C++14
0 / 100
 12 ms 8056 KB 
#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];
ll ans[Maxn], dep[Maxn];

void DFS(ll u, ll d = 1){
	dep[u] = d;
	R[u].pb(0);
	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());
}
ll s;
ll cnt[1000010];
bool check(ll x){
	if(x < 0) return false;
	return (cnt[x] > 0);
}

void DFS2(ll u){
	for(auto x: R[u]) cnt[x] ++;
	
	for(auto X : Q[u]){
		ll x = X.F - dep[u];
		//cerr << u << ' ' << X.F << ' ' << x << '\n';
		if(x >= s + 1) ans[X.S] = (cnt[x - (s + 1)] > 0);
		/*for(int i = 1; i * i <= x; i++){
			if(x % i == 0){
				ans[X.S] |= check(i - (s + 1));
				ans[X.S] |= check((x / i) - (s + 1));
			}
		}*/
		if(x == 0) ans[X.S] = true;
	}
	
	for(auto E : G[u]){
		DFS2(E.F);
	}
	
	for(auto x : R[u]) cnt[x] --;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m, k;
	cin >> n >> m >> k >> s;
	ll p, l;
	for(int i = 1; i <= n; i++){
		cin >> p >> l;
		G[p].pb({i, l + (p != 0)});
	}
	for(int i = 1; i <= m; i++){
		cin >> p >> l;
		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

*/

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 8056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -