oj.uz

Submission #158664

# Submission time Handle Problem Language Result Execution time Memory
158664 2019-10-18T10:26:13 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 201 ms 76068 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];
bool mark[MAXN];
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("input.txt", "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++;
	mark[0]=1;
	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) mark[L[i]]=1;
		
	}
	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;
		
		// tool | k - (L[x]+y)
		
		for (int tmp=X[i]; !ans[i]; tmp=P[tmp]){
			if (mark[k-(s+Y[i]+L[X[i]]-L[tmp])]) ans[i]=1;
			if (!tmp) break ;
		}
		if (ans[i]) continue ;
		
		query[x].pb({y, i});
	}
	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 66 ms 70776 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 75568 KB Output is correct
2 Correct 76 ms 75560 KB Output is correct
3 Correct 76 ms 75768 KB Output is correct
4 Correct 75 ms 75640 KB Output is correct
5 Correct 200 ms 75640 KB Output is correct
6 Correct 201 ms 76068 KB Output is correct
7 Correct 151 ms 75512 KB Output is correct
8 Correct 146 ms 75928 KB Output is correct
9 Correct 76 ms 75128 KB Output is correct
10 Correct 75 ms 74616 KB Output is correct
11 Correct 71 ms 71032 KB Output is correct
12 Correct 177 ms 72824 KB Output is correct

Subtask #3
0 / 34.0

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