Submission #953122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953122	2024-03-25T14:25:46 Z	PM1	File Paths (BOI15_fil)	C++17	33 / 100	128 ms	4920 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<=k)
		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++;
	for(int i=1;i<=n+m;i++){
		int x,y;
		cin>>x>>y;
		par[i]=x;
		dis[i]=dis[x]+y+1;
		v[x].push_back(i);
		if(i<=n)
			all.push_back(dis[i]);
	}
	all.push_back(0);
	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	604 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	21 ms	4676 KB	Output is correct
2	Correct	19 ms	4684 KB	Output is correct
3	Correct	19 ms	4444 KB	Output is correct
4	Correct	21 ms	4584 KB	Output is correct
5	Correct	106 ms	4772 KB	Output is correct
6	Correct	128 ms	4920 KB	Output is correct
7	Correct	68 ms	4708 KB	Output is correct
8	Correct	67 ms	4708 KB	Output is correct
9	Correct	20 ms	4444 KB	Output is correct
10	Correct	17 ms	4444 KB	Output is correct
11	Correct	16 ms	856 KB	Output is correct
12	Correct	104 ms	4364 KB	Output is correct

Subtask #3

0 / 34.0

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