Submission #949240

#	Time	Username	Problem	Language	Result	Execution time	Memory
949240		MuhammadSaram	File Paths (BOI15_fil)	C++17	0 / 100	16 ms	348 KiB

fil

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
#define in binary_search
#define int long long

int s;

bool check(vector<int> &v,int x)
{
	if (x<s+1)
		return false;
	x-=s+1;
	for (int i=v.size()-2;v[i]>=x;i--)
		if (in(all(v),v[i]-x))
			return true;
	return false;
}

signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	cin>>s;
	int pd[n+1]={},pathd[n+1]={};
	int pathf[m];
	for (int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		pd[i]=a;
		pathd[i]=pathd[a]+b+1;
	}
	for (int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		pathf[i]=pathd[a]+b+1;
		vector<int> v;
		v.push_back(pathf[i]);
		while (a)
		{
			v.push_back(pathd[a]);
			a=pd[a];
		}
		v.push_back(0);
		sort(all(v));
		string ans="NO";
		cout<<pathf[i]<<endl;
		if (pathf[i]==k)
			ans="YES";
		else if(pathf[i]>k)
		{
			int tosub=pathf[i]-k+s+1;
			for (int i=v.size()-2;v[i]>=tosub;i--)
				if (in(all(v),v[i]-tosub))
				{
					ans="YES";
					break;
				}
		}
		else
		{
			int toadd=k-pathf[i];
			for (int i=1;i*i<=toadd;i++)
				if (toadd%i==0)
				{
					if (check(v,i) or check(v,toadd/i))
					{
						ans="YES";
						break;
					}
				}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34