oj.uz

Submission #158619

# Submission time Handle Problem Language Result Execution time Memory
158619 2019-10-18T07:08:55 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 327 ms 95096 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;
vector<int> V[MAXN];

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]++;
			V[tmp].pb(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 x:V[node]) cnt[x]--;
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 70904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 74876 KB Output is correct
2 Correct 74 ms 74744 KB Output is correct
3 Correct 76 ms 75000 KB Output is correct
4 Correct 75 ms 75000 KB Output is correct
5 Correct 276 ms 94472 KB Output is correct
6 Correct 274 ms 95096 KB Output is correct
7 Correct 182 ms 85496 KB Output is correct
8 Correct 180 ms 85792 KB Output is correct
9 Correct 75 ms 74488 KB Output is correct
10 Correct 75 ms 73976 KB Output is correct
11 Correct 72 ms 71736 KB Output is correct
12 Correct 327 ms 91872 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 70904 KB Output isn't correct
2 Halted 0 ms 0 KB -