oj.uz

답안 #953148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953148 2024-03-25T14:47:34 Z PM1 File Paths (BOI15_fil) C++17
33 / 100
 107 ms 4944 KB 
#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++;
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4444 KB Output is correct
2 Correct 19 ms 4444 KB Output is correct
3 Correct 19 ms 4444 KB Output is correct
4 Correct 20 ms 4508 KB Output is correct
5 Correct 107 ms 4700 KB Output is correct
6 Correct 104 ms 4688 KB Output is correct
7 Correct 69 ms 4944 KB Output is correct
8 Correct 68 ms 4696 KB Output is correct
9 Correct 20 ms 4444 KB Output is correct
10 Correct 17 ms 4440 KB Output is correct
11 Correct 13 ms 860 KB Output is correct
12 Correct 95 ms 4384 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -