oj.uz

Submission #250282

# Submission time Handle Problem Language Result Execution time Memory
250282 2020-07-17T10:36:44 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 104952 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];
bool turi(const vector<int>&a, const vector<int>&b)
{
	int i = 0;
	int j = 0;
	while (i < (int)a.size() && j < (int)b.size())
	{
		if (a[i] == b[j])
			return true;
		if (a[i] < b[j])
			i++;
		else
			j++;
	}
	return false;
}
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];
		if (dal[ilg].size() <= 10)
		{
			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;
		}
		else
		{
			if (turi(dal[ilg], cikl[v]))
				return true;
			vector<int>x;
			for (int c : dal[ilg])
				x.push_back(ilg / c);
			reverse(x.begin(), x.end());
			return turi(x, cikl[v]);
		}
	};
	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 692 ms 84600 KB Output is correct
2 Correct 544 ms 84636 KB Output is correct
3 Correct 584 ms 84752 KB Output is correct
4 Correct 548 ms 85104 KB Output is correct
5 Correct 536 ms 84744 KB Output is correct
6 Correct 540 ms 84728 KB Output is correct
7 Correct 616 ms 85368 KB Output is correct
8 Correct 528 ms 84728 KB Output is correct
9 Correct 599 ms 84728 KB Output is correct
10 Correct 527 ms 84732 KB Output is correct
11 Correct 697 ms 84640 KB Output is correct
12 Correct 709 ms 85112 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 84744 KB Output is correct
2 Correct 643 ms 84736 KB Output is correct
3 Correct 593 ms 84856 KB Output is correct
4 Correct 662 ms 84860 KB Output is correct
5 Execution timed out 1026 ms 104952 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 84600 KB Output is correct
2 Correct 544 ms 84636 KB Output is correct
3 Correct 584 ms 84752 KB Output is correct
4 Correct 548 ms 85104 KB Output is correct
5 Correct 536 ms 84744 KB Output is correct
6 Correct 540 ms 84728 KB Output is correct
7 Correct 616 ms 85368 KB Output is correct
8 Correct 528 ms 84728 KB Output is correct
9 Correct 599 ms 84728 KB Output is correct
10 Correct 527 ms 84732 KB Output is correct
11 Correct 697 ms 84640 KB Output is correct
12 Correct 709 ms 85112 KB Output is correct
13 Correct 530 ms 84744 KB Output is correct
14 Correct 643 ms 84736 KB Output is correct
15 Correct 593 ms 84856 KB Output is correct
16 Correct 662 ms 84860 KB Output is correct
17 Execution timed out 1026 ms 104952 KB Time limit exceeded
18 Halted 0 ms 0 KB -