oj.uz

Submission #250382

# Submission time Handle Problem Language Result Execution time Memory
250382 2020-07-17T16:12:34 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 182420 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];
bitset<200000000>a1, a2, a3, a4;
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++;
	ll 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]);
	}
	vector<ll>cikl;
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			ll x = j + ((d[i] - d[j] + s) << 20);
			a1[x % 200000000] = true;
			a2[x % 199999999] = true;
			a3[x % 199592979] = true;
			a4[x % 195172978] = true;
		}
	}
	sort(D.begin(), D.end());
	sort(cikl.begin(), cikl.end());
	function<bool(int, ll)>ok = [&](int v, ll 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 (ilg - s >= 1 && binary_search(D.begin(), D.end(), ilg - s))
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (ll c : dal[ilg])
		{
			ll x1 = v + (c << 20);
			ll x2 = v + ((ilg / c) << 20);
			if (a1[x1 % 200000000] && a2[x1 % 199999999] && a3[x1 % 199592979] && a4[x1 % 195172978])
				return true;
			if (a1[x2 % 200000000] && a2[x2 % 199999999] && a3[x2 % 199592979] && a4[x2 % 195172978])
				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 653 ms 87544 KB Output is correct
2 Correct 544 ms 94712 KB Output is correct
3 Correct 725 ms 102008 KB Output is correct
4 Correct 688 ms 182008 KB Output is correct
5 Correct 609 ms 178424 KB Output is correct
6 Correct 553 ms 140920 KB Output is correct
7 Correct 585 ms 181896 KB Output is correct
8 Correct 580 ms 113512 KB Output is correct
9 Correct 582 ms 113004 KB Output is correct
10 Correct 656 ms 84856 KB Output is correct
11 Correct 573 ms 103568 KB Output is correct
12 Correct 618 ms 181996 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 139384 KB Output is correct
2 Correct 601 ms 136824 KB Output is correct
3 Correct 598 ms 137336 KB Output is correct
4 Correct 590 ms 140664 KB Output is correct
5 Correct 975 ms 182292 KB Output is correct
6 Execution timed out 1105 ms 182420 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 87544 KB Output is correct
2 Correct 544 ms 94712 KB Output is correct
3 Correct 725 ms 102008 KB Output is correct
4 Correct 688 ms 182008 KB Output is correct
5 Correct 609 ms 178424 KB Output is correct
6 Correct 553 ms 140920 KB Output is correct
7 Correct 585 ms 181896 KB Output is correct
8 Correct 580 ms 113512 KB Output is correct
9 Correct 582 ms 113004 KB Output is correct
10 Correct 656 ms 84856 KB Output is correct
11 Correct 573 ms 103568 KB Output is correct
12 Correct 618 ms 181996 KB Output is correct
13 Correct 569 ms 139384 KB Output is correct
14 Correct 601 ms 136824 KB Output is correct
15 Correct 598 ms 137336 KB Output is correct
16 Correct 590 ms 140664 KB Output is correct
17 Correct 975 ms 182292 KB Output is correct
18 Execution timed out 1105 ms 182420 KB Time limit exceeded
19 Halted 0 ms 0 KB -