oj.uz

Submission #158621

# Submission time Handle Problem Language Result Execution time Memory
158621 2019-10-18T07:15:12 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 318 ms 94932 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;
int 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;
		if (L[i]>MAXN) L[i]=MAXN+10;
		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 66 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 75 ms 74872 KB Output is correct
2 Correct 75 ms 74744 KB Output is correct
3 Correct 79 ms 74968 KB Output is correct
4 Correct 75 ms 74872 KB Output is correct
5 Correct 281 ms 94540 KB Output is correct
6 Correct 269 ms 94932 KB Output is correct
7 Correct 179 ms 85516 KB Output is correct
8 Correct 200 ms 85864 KB Output is correct
9 Correct 78 ms 74488 KB Output is correct
10 Correct 75 ms 73960 KB Output is correct
11 Correct 72 ms 71672 KB Output is correct
12 Correct 318 ms 91764 KB Output is correct

Subtask #3
0 / 34.0

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