oj.uz

Submission #250275

# Submission time Handle Problem Language Result Execution time Memory
250275 2020-07-17T10:28:02 Z tutis File Paths (BOI15_fil) C++17
66 / 100
 1000 ms 104964 KB 
/*input
2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

*/
#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 695 ms 84632 KB Output is correct
2 Correct 606 ms 84688 KB Output is correct
3 Correct 633 ms 84688 KB Output is correct
4 Correct 641 ms 84984 KB Output is correct
5 Correct 625 ms 84792 KB Output is correct
6 Correct 787 ms 84600 KB Output is correct
7 Correct 776 ms 85272 KB Output is correct
8 Correct 679 ms 84708 KB Output is correct
9 Correct 792 ms 84632 KB Output is correct
10 Correct 707 ms 84564 KB Output is correct
11 Correct 669 ms 84700 KB Output is correct
12 Correct 621 ms 85112 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 84820 KB Output is correct
2 Correct 773 ms 84840 KB Output is correct
3 Correct 721 ms 84756 KB Output is correct
4 Correct 646 ms 84792 KB Output is correct
5 Correct 968 ms 104768 KB Output is correct
6 Correct 883 ms 104752 KB Output is correct
7 Correct 929 ms 95876 KB Output is correct
8 Correct 849 ms 95944 KB Output is correct
9 Correct 634 ms 85020 KB Output is correct
10 Correct 602 ms 84864 KB Output is correct
11 Correct 618 ms 85516 KB Output is correct
12 Correct 939 ms 103928 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 84632 KB Output is correct
2 Correct 606 ms 84688 KB Output is correct
3 Correct 633 ms 84688 KB Output is correct
4 Correct 641 ms 84984 KB Output is correct
5 Correct 625 ms 84792 KB Output is correct
6 Correct 787 ms 84600 KB Output is correct
7 Correct 776 ms 85272 KB Output is correct
8 Correct 679 ms 84708 KB Output is correct
9 Correct 792 ms 84632 KB Output is correct
10 Correct 707 ms 84564 KB Output is correct
11 Correct 669 ms 84700 KB Output is correct
12 Correct 621 ms 85112 KB Output is correct
13 Correct 635 ms 84820 KB Output is correct
14 Correct 773 ms 84840 KB Output is correct
15 Correct 721 ms 84756 KB Output is correct
16 Correct 646 ms 84792 KB Output is correct
17 Correct 968 ms 104768 KB Output is correct
18 Correct 883 ms 104752 KB Output is correct
19 Correct 929 ms 95876 KB Output is correct
20 Correct 849 ms 95944 KB Output is correct
21 Correct 634 ms 85020 KB Output is correct
22 Correct 602 ms 84864 KB Output is correct
23 Correct 618 ms 85516 KB Output is correct
24 Correct 939 ms 103928 KB Output is correct
25 Correct 745 ms 84984 KB Output is correct
26 Correct 612 ms 84856 KB Output is correct
27 Correct 736 ms 84984 KB Output is correct
28 Correct 618 ms 84856 KB Output is correct
29 Correct 897 ms 104824 KB Output is correct
30 Execution timed out 1029 ms 104964 KB Time limit exceeded
31 Halted 0 ms 0 KB -