oj.uz

Submission #250395

# Submission time Handle Problem Language Result Execution time Memory
250395 2020-07-17T16:50:33 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 707 ms 85112 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++)
	{
		int kiek = 0;
		for (int j = i; j != -1; j = p[j])
		{
			kiek++;
			cikl[j].push_back(d[i] - d[j] + s);
			if (kiek == 2)
				break;
		}
	}
	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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 84784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 84856 KB Output is correct
2 Correct 534 ms 84764 KB Output is correct
3 Correct 550 ms 84856 KB Output is correct
4 Correct 602 ms 84984 KB Output is correct
5 Correct 621 ms 85112 KB Output is correct
6 Correct 613 ms 84996 KB Output is correct
7 Correct 612 ms 84856 KB Output is correct
8 Correct 603 ms 84984 KB Output is correct
9 Correct 528 ms 84856 KB Output is correct
10 Correct 526 ms 84856 KB Output is correct
11 Correct 558 ms 84856 KB Output is correct
12 Correct 664 ms 85112 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 84784 KB Output isn't correct
2 Halted 0 ms 0 KB -