Submission #250373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250373	2020-07-17T16:00:36 Z	tutis	File Paths (BOI15_fil)	C++17	33 / 100	862 ms	87952 KB

fil

/*input
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int>dal[1000001];
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0), cerr.tie(0);
	for (int i = 1; i <= 1000; i++)
		for (int j = i * i; j <= 1000000; j += i)
			dal[j].push_back(i);
	int n, m, k, s;
	cin >> n >> m >> k >> s;
	s++;
	ll p[n + 1], d[n + 1], l[n + 1];
	p[0] = -1;
	d[0] = 1;
	cc_hash_table<int, bool>D;
	D.insert({1, true});
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i] >> l[i];
		d[i] = d[p[i]] + 1 + l[i];
		D[d[i]] = true;
	}
	cc_hash_table<ll, bool>cikl;
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			cikl[j + ((d[i] - d[j] + s) << 10)] = true;
		}
	}
	function<bool(int, ll)>ok = [&](int v, ll ilg)
	{
		if (d[v] == ilg)
			return true;
		if (ilg <= 0)
			return false;
		if (v != 0 && ok(p[v], ilg - 1 - l[v]))
			return true;
		if (D.find(ilg - s) != D.end())
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (ll c : dal[ilg])
		{
			if (cikl.find(v + (c << 10)) != cikl.end())
				return true;
			if (cikl.find(v + ((ilg / c) << 10)) != cikl.end())
				return true;
		}
		return false;
	};
	while (m--)
	{
		int p, l;
		cin >> p >> l;
		if (ok(p, k - l))
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}

Subtask #1

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	682 ms	84856 KB	Output is correct
2	Correct	629 ms	84856 KB	Output is correct
3	Correct	641 ms	84856 KB	Output is correct
4	Correct	656 ms	87800 KB	Output is correct
5	Correct	770 ms	85568 KB	Output is correct
6	Correct	813 ms	84984 KB	Output is correct
7	Correct	862 ms	87952 KB	Output is correct
8	Correct	631 ms	84856 KB	Output is correct
9	Correct	652 ms	84868 KB	Output is correct
10	Correct	679 ms	84728 KB	Output is correct
11	Correct	808 ms	84728 KB	Output is correct
12	Correct	829 ms	87936 KB	Output is correct

Subtask #2

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	835 ms	84984 KB	Output is correct
2	Correct	705 ms	85112 KB	Output is correct
3	Incorrect	706 ms	85116 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	682 ms	84856 KB	Output is correct
2	Correct	629 ms	84856 KB	Output is correct
3	Correct	641 ms	84856 KB	Output is correct
4	Correct	656 ms	87800 KB	Output is correct
5	Correct	770 ms	85568 KB	Output is correct
6	Correct	813 ms	84984 KB	Output is correct
7	Correct	862 ms	87952 KB	Output is correct
8	Correct	631 ms	84856 KB	Output is correct
9	Correct	652 ms	84868 KB	Output is correct
10	Correct	679 ms	84728 KB	Output is correct
11	Correct	808 ms	84728 KB	Output is correct
12	Correct	829 ms	87936 KB	Output is correct
13	Correct	835 ms	84984 KB	Output is correct
14	Correct	705 ms	85112 KB	Output is correct
15	Incorrect	706 ms	85116 KB	Output isn't correct
16	Halted	0 ms	0 KB	-