oj.uz

Submission #250369

# Submission time Handle Problem Language Result Execution time Memory
250369 2020-07-17T15:51:36 Z tutis File Paths (BOI15_fil) C++17
100 / 100
 965 ms 109176 KB 
/*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>
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++;
	int p[n + 1], d[n + 1], l[n + 1];
	p[0] = -1;
	d[0] = 1;
	vector<int>D = {1};
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i] >> l[i];
		d[i] = d[p[i]] + 1 + l[i];
		D.push_back(d[i]);
	}
	sort(D.begin(), D.end());
	vector<int>cikl[n + 1];
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			cikl[j].push_back(d[i] - d[j] + s);
		}
	}
	for (int i = 0; i <= n; i++)
		sort(cikl[i].begin(), cikl[i].end());
	function<bool(int, int)>ok = [&](int v, int 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 (binary_search(D.begin(), D.end(), ilg - s))
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (int c : dal[ilg])
		{
			if (binary_search(cikl[v].begin(), cikl[v].end(), c))
				return true;
			if (binary_search(cikl[v].begin(), cikl[v].end(), ilg / c))
				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 519 ms 84636 KB Output is correct
2 Correct 533 ms 84784 KB Output is correct
3 Correct 511 ms 84600 KB Output is correct
4 Correct 527 ms 85240 KB Output is correct
5 Correct 546 ms 85048 KB Output is correct
6 Correct 525 ms 84600 KB Output is correct
7 Correct 579 ms 85368 KB Output is correct
8 Correct 567 ms 84728 KB Output is correct
9 Correct 505 ms 84600 KB Output is correct
10 Correct 534 ms 84600 KB Output is correct
11 Correct 555 ms 84600 KB Output is correct
12 Correct 523 ms 85116 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 85008 KB Output is correct
2 Correct 522 ms 84856 KB Output is correct
3 Correct 516 ms 84856 KB Output is correct
4 Correct 521 ms 84856 KB Output is correct
5 Correct 844 ms 104856 KB Output is correct
6 Correct 801 ms 104696 KB Output is correct
7 Correct 768 ms 95992 KB Output is correct
8 Correct 760 ms 96064 KB Output is correct
9 Correct 564 ms 84988 KB Output is correct
10 Correct 522 ms 84856 KB Output is correct
11 Correct 519 ms 85368 KB Output is correct
12 Correct 810 ms 104036 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 84636 KB Output is correct
2 Correct 533 ms 84784 KB Output is correct
3 Correct 511 ms 84600 KB Output is correct
4 Correct 527 ms 85240 KB Output is correct
5 Correct 546 ms 85048 KB Output is correct
6 Correct 525 ms 84600 KB Output is correct
7 Correct 579 ms 85368 KB Output is correct
8 Correct 567 ms 84728 KB Output is correct
9 Correct 505 ms 84600 KB Output is correct
10 Correct 534 ms 84600 KB Output is correct
11 Correct 555 ms 84600 KB Output is correct
12 Correct 523 ms 85116 KB Output is correct
13 Correct 660 ms 85008 KB Output is correct
14 Correct 522 ms 84856 KB Output is correct
15 Correct 516 ms 84856 KB Output is correct
16 Correct 521 ms 84856 KB Output is correct
17 Correct 844 ms 104856 KB Output is correct
18 Correct 801 ms 104696 KB Output is correct
19 Correct 768 ms 95992 KB Output is correct
20 Correct 760 ms 96064 KB Output is correct
21 Correct 564 ms 84988 KB Output is correct
22 Correct 522 ms 84856 KB Output is correct
23 Correct 519 ms 85368 KB Output is correct
24 Correct 810 ms 104036 KB Output is correct
25 Correct 639 ms 84860 KB Output is correct
26 Correct 517 ms 84856 KB Output is correct
27 Correct 518 ms 84860 KB Output is correct
28 Correct 516 ms 84924 KB Output is correct
29 Correct 784 ms 104696 KB Output is correct
30 Correct 806 ms 104828 KB Output is correct
31 Correct 822 ms 95956 KB Output is correct
32 Correct 743 ms 95736 KB Output is correct
33 Correct 528 ms 84952 KB Output is correct
34 Correct 625 ms 84984 KB Output is correct
35 Correct 535 ms 85496 KB Output is correct
36 Correct 965 ms 109176 KB Output is correct