oj.uz

답안 #158617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158617 2019-10-18T07:04:11 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 210 ms 51788 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 1000010, LOG=20;

int n, m, k, s, u, v, x, y, t, a, b;
ll L[MAXN], P[MAXN];
int cnt[MAXN];
bool ans[MAXN];
int X[MAXN], Y[MAXN];
set<ll> st;
vector<int> G[MAXN];
vector<pll> query[MAXN];
vector<int> vec;

void shit(int x){
	vec.clear();
	for (int i=1; i*i<=x; i++) if (x%i==0){
		vec.pb(i);
		vec.pb(x/i);
	}
}

void dfs(int node){
	for (int tmp=node; ; tmp=P[tmp]){
		int x=L[node]-L[tmp]+s;
		if (x<MAXN) cnt[x]++;
		if (!tmp) break ;
	}
	for (pii p:query[node]){
		shit(p.first);
		for (int d:vec) if (cnt[d]>0){
			ans[p.second]=1;
			break ;
		}
	}
	for (int v:G[node]) dfs(v);
	
	for (int tmp=node; ; tmp=P[tmp]){
		int x=L[node]-L[tmp]+s;
		if (x<MAXN) cnt[x]--;
		if (!tmp) break ;
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("fil1a.in", "r", stdin);
	//freopen("output.txt", "w", stdout);
	//for (int i=1; i<MAXN; i++) for (int j=i; j<MAXN; j+=i) D[j].pb(i);
	cin>>n>>m>>k>>s;
	s++;
	st.insert(0);
	for (int i=1; i<=n; i++){
		cin>>P[i]>>L[i];
		G[P[i]].pb(i);
		L[i]+=L[P[i]]+1;
		st.insert(L[i]);
	}
	for (int i=1; i<=m; i++){
		cin>>x>>y;
		X[i]=x;Y[i]=++y;
		y+=L[x];
		y=k-y;
		if (y<0) continue ;
		if (y==0) ans[i]=1;
		
		for (int tmp=X[i]; !ans[i]; tmp=P[tmp]){
			if (st.count(k-(s+Y[i]+L[X[i]]-L[tmp]))) ans[i]=1;
			if (!tmp) break ;
		}
		if (ans[i]) continue ;
		
		query[x].pb({y, i});
	}
	
	st.clear();
	dfs(0);
	
	for (int i=1; i<=m; i++){
		if (ans[i]) cout<<"YES\n";
		else cout<<"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 45 ms 47324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 51356 KB Output is correct
2 Correct 54 ms 51300 KB Output is correct
3 Correct 53 ms 51448 KB Output is correct
4 Correct 53 ms 51448 KB Output is correct
5 Correct 167 ms 51712 KB Output is correct
6 Correct 156 ms 51788 KB Output is correct
7 Correct 127 ms 51320 KB Output is correct
8 Correct 127 ms 51620 KB Output is correct
9 Correct 54 ms 51064 KB Output is correct
10 Correct 53 ms 50552 KB Output is correct
11 Correct 49 ms 47716 KB Output is correct
12 Correct 210 ms 49144 KB Output is correct

Subtask #3
0 / 34.0

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