oj.uz

Submission #250279

# Submission time Handle Problem Language Result Execution time Memory
250279 2020-07-17T10:34:29 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 105048 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];
		vector<int>x;
		for (int c : dal[ilg])
			x.push_back(ilg / c);
		reverse(x.begin(), x.end());
		if (turi(x, cikl[v]) || turi(dal[ilg], cikl[v]))
			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 527 ms 84600 KB Output is correct
2 Correct 531 ms 84600 KB Output is correct
3 Correct 534 ms 84728 KB Output is correct
4 Correct 536 ms 85112 KB Output is correct
5 Correct 530 ms 84728 KB Output is correct
6 Correct 537 ms 84772 KB Output is correct
7 Correct 555 ms 85368 KB Output is correct
8 Correct 548 ms 84584 KB Output is correct
9 Correct 547 ms 84672 KB Output is correct
10 Correct 543 ms 84728 KB Output is correct
11 Correct 687 ms 84728 KB Output is correct
12 Correct 628 ms 85212 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 84984 KB Output is correct
2 Correct 536 ms 84728 KB Output is correct
3 Correct 569 ms 84856 KB Output is correct
4 Correct 545 ms 84956 KB Output is correct
5 Execution timed out 1096 ms 105048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 84600 KB Output is correct
2 Correct 531 ms 84600 KB Output is correct
3 Correct 534 ms 84728 KB Output is correct
4 Correct 536 ms 85112 KB Output is correct
5 Correct 530 ms 84728 KB Output is correct
6 Correct 537 ms 84772 KB Output is correct
7 Correct 555 ms 85368 KB Output is correct
8 Correct 548 ms 84584 KB Output is correct
9 Correct 547 ms 84672 KB Output is correct
10 Correct 543 ms 84728 KB Output is correct
11 Correct 687 ms 84728 KB Output is correct
12 Correct 628 ms 85212 KB Output is correct
13 Correct 592 ms 84984 KB Output is correct
14 Correct 536 ms 84728 KB Output is correct
15 Correct 569 ms 84856 KB Output is correct
16 Correct 545 ms 84956 KB Output is correct
17 Execution timed out 1096 ms 105048 KB Time limit exceeded
18 Halted 0 ms 0 KB -