oj.uz

Submission #250370

# Submission time Handle Problem Language Result Execution time Memory
250370 2020-07-17T15:57:02 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 186872 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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
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;
	cc_hash_table<int, bool>D;
	D.insert({1, true});
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i] >> l[i];
		d[i] = d[p[i]] + 1 + l[i];
		D[d[i]] = true;
	}
	cc_hash_table<int, bool>cikl[n + 1];
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			cikl[j][d[i] - d[j] + s] = true;
		}
	}
	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 (D.find(ilg - s) != D.end())
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (int c : dal[ilg])
		{
			if (cikl[v].find(c) != cikl[v].end())
				return true;
			if (cikl[v].find(ilg / c) != cikl[v].end())
				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 642 ms 84604 KB Output is correct
2 Correct 605 ms 84788 KB Output is correct
3 Correct 636 ms 84900 KB Output is correct
4 Correct 647 ms 86236 KB Output is correct
5 Correct 614 ms 85240 KB Output is correct
6 Correct 615 ms 84984 KB Output is correct
7 Correct 666 ms 87288 KB Output is correct
8 Correct 611 ms 84768 KB Output is correct
9 Correct 616 ms 84856 KB Output is correct
10 Correct 610 ms 84604 KB Output is correct
11 Correct 621 ms 84896 KB Output is correct
12 Correct 636 ms 86648 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 85112 KB Output is correct
2 Correct 661 ms 85112 KB Output is correct
3 Correct 643 ms 85368 KB Output is correct
4 Correct 644 ms 85380 KB Output is correct
5 Execution timed out 1114 ms 186872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 84604 KB Output is correct
2 Correct 605 ms 84788 KB Output is correct
3 Correct 636 ms 84900 KB Output is correct
4 Correct 647 ms 86236 KB Output is correct
5 Correct 614 ms 85240 KB Output is correct
6 Correct 615 ms 84984 KB Output is correct
7 Correct 666 ms 87288 KB Output is correct
8 Correct 611 ms 84768 KB Output is correct
9 Correct 616 ms 84856 KB Output is correct
10 Correct 610 ms 84604 KB Output is correct
11 Correct 621 ms 84896 KB Output is correct
12 Correct 636 ms 86648 KB Output is correct
13 Correct 639 ms 85112 KB Output is correct
14 Correct 661 ms 85112 KB Output is correct
15 Correct 643 ms 85368 KB Output is correct
16 Correct 644 ms 85380 KB Output is correct
17 Execution timed out 1114 ms 186872 KB Time limit exceeded
18 Halted 0 ms 0 KB -