Submission #953152

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953152	2024-03-25T14:54:39 Z	PM1	File Paths (BOI15_fil)	C++17	33 / 100	113 ms	4952 KB

fil

#include <bits/stdc++.h>
using namespace std;
const int mxn=3e3+5,mxs=1e6+5;
int n,m,s,k,par[mxn*2],dis[mxn*2];
vector<int>all,v[mxn*2];
int mark[mxs],ans[mxn*2];
void make(int x,bool y){
	int z=x;
	while(x!=0){
		x=par[x];
		int d=dis[z]-dis[x];
		if(d<=k)mark[d]=y;
	}
}
void dfs1(int z,int g,int x){
	if(z>n)
		return ;
	x+=dis[z]-dis[par[z]];
	if(x<mxs)
		mark[x]+=g;
	for(auto i:v[z])
		dfs1(i,g,x);
}
void dfs(int z){
	if(z>n){
		int x=k-dis[z];
		for(int i=1;i*i<=x;i++){
			if(x%i==0 &&(mark[i] || mark[x/i]))ans[z]=1;
		}
	}
	dfs1(z,1,s);
	for(auto i:v[z])
		dfs(i);
	dfs1(z,-1,s);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>s;
	s++;
	dis[0]=1;
	for(int i=1;i<=n+m;i++){
		int x,y;
		cin>>x>>y;
		par[i]=x;
		dis[i]=dis[x]+y;
		v[x].push_back(i);
		if(i<=n){
			dis[i]++;
			all.push_back(dis[i]);
		}
	}
	all.push_back(1);
	for(int i=n+1;i<=n+m;i++){
		make(i,1);
		if(dis[i]==k)ans[i]=1;
		for(auto j:all){
			int res=k-j-s;
			if(res>=0 && mark[res])ans[i]=1;
		}
		make(i,0);
	}
	dfs(0);
	for(int i=n+1;i<=n+m;i++){
		if(ans[i])
			cout<<"YES"<<'\n';
		else
			cout<<"NO"<<'\n';
	}
	return 0;
}

Subtask #1

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	600 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	18 ms	4460 KB	Output is correct
2	Correct	19 ms	4444 KB	Output is correct
3	Correct	19 ms	4444 KB	Output is correct
4	Correct	18 ms	4440 KB	Output is correct
5	Correct	113 ms	4952 KB	Output is correct
6	Correct	100 ms	4772 KB	Output is correct
7	Correct	70 ms	4688 KB	Output is correct
8	Correct	65 ms	4680 KB	Output is correct
9	Correct	19 ms	4444 KB	Output is correct
10	Correct	17 ms	4444 KB	Output is correct
11	Correct	11 ms	868 KB	Output is correct
12	Correct	92 ms	4380 KB	Output is correct

Subtask #3

0 / 34.0

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