oj.uz

Submission #250276

# Submission time Handle Problem Language Result Execution time Memory
250276 2020-07-17T10:28:36 Z tutis File Paths (BOI15_fil) C++17
66 / 100
 1000 ms 109304 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 544 ms 84728 KB Output is correct
2 Correct 640 ms 84728 KB Output is correct
3 Correct 698 ms 84604 KB Output is correct
4 Correct 760 ms 84984 KB Output is correct
5 Correct 548 ms 84876 KB Output is correct
6 Correct 528 ms 84728 KB Output is correct
7 Correct 542 ms 85240 KB Output is correct
8 Correct 520 ms 84576 KB Output is correct
9 Correct 522 ms 84600 KB Output is correct
10 Correct 685 ms 84696 KB Output is correct
11 Correct 532 ms 84728 KB Output is correct
12 Correct 532 ms 85212 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 84720 KB Output is correct
2 Correct 584 ms 84984 KB Output is correct
3 Correct 528 ms 84728 KB Output is correct
4 Correct 526 ms 84856 KB Output is correct
5 Correct 868 ms 104700 KB Output is correct
6 Correct 792 ms 104668 KB Output is correct
7 Correct 903 ms 95972 KB Output is correct
8 Correct 745 ms 95992 KB Output is correct
9 Correct 533 ms 84872 KB Output is correct
10 Correct 536 ms 84860 KB Output is correct
11 Correct 572 ms 85440 KB Output is correct
12 Correct 871 ms 104184 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 84728 KB Output is correct
2 Correct 640 ms 84728 KB Output is correct
3 Correct 698 ms 84604 KB Output is correct
4 Correct 760 ms 84984 KB Output is correct
5 Correct 548 ms 84876 KB Output is correct
6 Correct 528 ms 84728 KB Output is correct
7 Correct 542 ms 85240 KB Output is correct
8 Correct 520 ms 84576 KB Output is correct
9 Correct 522 ms 84600 KB Output is correct
10 Correct 685 ms 84696 KB Output is correct
11 Correct 532 ms 84728 KB Output is correct
12 Correct 532 ms 85212 KB Output is correct
13 Correct 544 ms 84720 KB Output is correct
14 Correct 584 ms 84984 KB Output is correct
15 Correct 528 ms 84728 KB Output is correct
16 Correct 526 ms 84856 KB Output is correct
17 Correct 868 ms 104700 KB Output is correct
18 Correct 792 ms 104668 KB Output is correct
19 Correct 903 ms 95972 KB Output is correct
20 Correct 745 ms 95992 KB Output is correct
21 Correct 533 ms 84872 KB Output is correct
22 Correct 536 ms 84860 KB Output is correct
23 Correct 572 ms 85440 KB Output is correct
24 Correct 871 ms 104184 KB Output is correct
25 Correct 651 ms 84728 KB Output is correct
26 Correct 532 ms 84728 KB Output is correct
27 Correct 626 ms 84856 KB Output is correct
28 Correct 527 ms 85112 KB Output is correct
29 Correct 925 ms 104824 KB Output is correct
30 Correct 857 ms 104952 KB Output is correct
31 Correct 878 ms 96120 KB Output is correct
32 Correct 783 ms 95864 KB Output is correct
33 Correct 628 ms 84976 KB Output is correct
34 Correct 539 ms 84864 KB Output is correct
35 Correct 549 ms 85332 KB Output is correct
36 Execution timed out 1094 ms 109304 KB Time limit exceeded