oj.uz

Submission #158662

# Submission time Handle Problem Language Result Execution time Memory
158662 2019-10-18T10:23:42 Z alishahali1382 File Paths (BOI15_fil) C++14
33 / 100
 202 ms 75992 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];
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;
		else L[i]=MAXN+10;
		
	}
	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 71 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 75512 KB Output is correct
2 Correct 76 ms 75436 KB Output is correct
3 Correct 86 ms 75768 KB Output is correct
4 Correct 76 ms 75640 KB Output is correct
5 Correct 202 ms 75796 KB Output is correct
6 Correct 196 ms 75992 KB Output is correct
7 Correct 142 ms 75516 KB Output is correct
8 Correct 146 ms 75868 KB Output is correct
9 Correct 76 ms 75228 KB Output is correct
10 Correct 76 ms 74620 KB Output is correct
11 Correct 72 ms 71032 KB Output is correct
12 Correct 173 ms 72824 KB Output is correct

Subtask #3
0 / 34.0

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