oj.uz

Submission #158628

# Submission time Handle Problem Language Result Execution time Memory
158628 2019-10-18T07:29:15 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 288 ms 75128 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> D;
vector<int> V[MAXN];

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

void dfs2(int node, int par, int val){
	int x=L[node]-L[par]+s;
	if (x<MAXN && node!=par) cnt[x]+=val;
	for (int v:G[node]) dfs2(v, par, val);
}

void dfs1(int node){
	dfs2(node, node, +1);
	for (pii p:query[node]){
		shit(p.first);
		for (int d:D) if (cnt[d]>0){
			ans[p.second]=1;
			break ;
		}
	}
	for (int v:G[node]) dfs1(v);
	dfs2(node, node, -1);
}

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();
	dfs1(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 70876 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 74728 KB Output is correct
2 Correct 74 ms 74720 KB Output is correct
3 Correct 74 ms 75000 KB Output is correct
4 Correct 74 ms 74872 KB Output is correct
5 Correct 272 ms 75000 KB Output is correct
6 Correct 262 ms 75128 KB Output is correct
7 Correct 198 ms 74840 KB Output is correct
8 Correct 204 ms 75112 KB Output is correct
9 Correct 75 ms 74488 KB Output is correct
10 Correct 74 ms 73848 KB Output is correct
11 Correct 72 ms 71140 KB Output is correct
12 Correct 288 ms 72568 KB Output is correct

Subtask #3
0 / 34.0

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