oj.uz

답안 #953122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953122 2024-03-25T14:25:46 Z PM1 File Paths (BOI15_fil) C++17
33 / 100
 128 ms 4920 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<=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

# 결과 실행 시간 메모리 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 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

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