oj.uz

Submission #250380

# Submission time Handle Problem Language Result Execution time Memory
250380 2020-07-17T16:11:00 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 133264 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<100000000>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 % 100000000] = true;
			a2[x % 99999999] = true;
			a3[x % 99592979] = true;
			a4[x % 95172978] = 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 % 100000000] && a2[x1 % 99999999] && a3[x1 % 99592979] && a4[x1 % 95172978])
				return true;
			if (a1[x2 % 100000000] && a2[x2 % 99999999] && a3[x2 % 99592979] && a4[x2 % 95172978])
				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 554 ms 87160 KB Output is correct
2 Correct 534 ms 94072 KB Output is correct
3 Correct 530 ms 100572 KB Output is correct
4 Correct 572 ms 132988 KB Output is correct
5 Correct 558 ms 132856 KB Output is correct
6 Correct 544 ms 124512 KB Output is correct
7 Correct 619 ms 133112 KB Output is correct
8 Correct 539 ms 109220 KB Output is correct
9 Correct 537 ms 108664 KB Output is correct
10 Correct 619 ms 84856 KB Output is correct
11 Correct 564 ms 102136 KB Output is correct
12 Correct 548 ms 132984 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 124248 KB Output is correct
2 Correct 651 ms 122744 KB Output is correct
3 Correct 645 ms 123000 KB Output is correct
4 Correct 557 ms 124408 KB Output is correct
5 Execution timed out 1012 ms 133264 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 87160 KB Output is correct
2 Correct 534 ms 94072 KB Output is correct
3 Correct 530 ms 100572 KB Output is correct
4 Correct 572 ms 132988 KB Output is correct
5 Correct 558 ms 132856 KB Output is correct
6 Correct 544 ms 124512 KB Output is correct
7 Correct 619 ms 133112 KB Output is correct
8 Correct 539 ms 109220 KB Output is correct
9 Correct 537 ms 108664 KB Output is correct
10 Correct 619 ms 84856 KB Output is correct
11 Correct 564 ms 102136 KB Output is correct
12 Correct 548 ms 132984 KB Output is correct
13 Correct 638 ms 124248 KB Output is correct
14 Correct 651 ms 122744 KB Output is correct
15 Correct 645 ms 123000 KB Output is correct
16 Correct 557 ms 124408 KB Output is correct
17 Execution timed out 1012 ms 133264 KB Time limit exceeded
18 Halted 0 ms 0 KB -