oj.uz

Submission #250270

# Submission time Handle Problem Language Result Execution time Memory
250270 2020-07-17T10:26:07 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 104780 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 (ll i = 1; i * i <= 1000000; i++)
		for (ll 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])
			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 651 ms 84688 KB Output is correct
2 Correct 681 ms 84572 KB Output is correct
3 Correct 683 ms 84808 KB Output is correct
4 Correct 680 ms 84968 KB Output is correct
5 Correct 837 ms 84916 KB Output is correct
6 Correct 852 ms 84728 KB Output is correct
7 Correct 730 ms 85240 KB Output is correct
8 Correct 670 ms 84768 KB Output is correct
9 Correct 765 ms 84728 KB Output is correct
10 Correct 630 ms 84704 KB Output is correct
11 Correct 636 ms 84732 KB Output is correct
12 Correct 734 ms 85112 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 85112 KB Output is correct
2 Correct 672 ms 84728 KB Output is correct
3 Correct 692 ms 84864 KB Output is correct
4 Correct 684 ms 84776 KB Output is correct
5 Execution timed out 1085 ms 104780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 84688 KB Output is correct
2 Correct 681 ms 84572 KB Output is correct
3 Correct 683 ms 84808 KB Output is correct
4 Correct 680 ms 84968 KB Output is correct
5 Correct 837 ms 84916 KB Output is correct
6 Correct 852 ms 84728 KB Output is correct
7 Correct 730 ms 85240 KB Output is correct
8 Correct 670 ms 84768 KB Output is correct
9 Correct 765 ms 84728 KB Output is correct
10 Correct 630 ms 84704 KB Output is correct
11 Correct 636 ms 84732 KB Output is correct
12 Correct 734 ms 85112 KB Output is correct
13 Correct 737 ms 85112 KB Output is correct
14 Correct 672 ms 84728 KB Output is correct
15 Correct 692 ms 84864 KB Output is correct
16 Correct 684 ms 84776 KB Output is correct
17 Execution timed out 1085 ms 104780 KB Time limit exceeded
18 Halted 0 ms 0 KB -