oj.uz

Submission #250379

# Submission time Handle Problem Language Result Execution time Memory
250379 2020-07-17T16:09:12 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 809 ms 121712 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>aaa;
bitset<100000000>bbb;
bitset<100000000>ccc;
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);
			aaa[x % 100000000] = true;
			bbb[x % 99999999] = true;
			ccc[x % 99592979] = 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 (aaa[x1 % 100000000] && bbb[x1 % 99999999] && ccc[x1 % 99592979])
				return true;
			if (aaa[x2 % 100000000] && bbb[x2 % 99999999] && ccc[x2 % 99592979])
				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 523 ms 86520 KB Output is correct
2 Correct 528 ms 91896 KB Output is correct
3 Correct 524 ms 96504 KB Output is correct
4 Correct 546 ms 121276 KB Output is correct
5 Correct 547 ms 121208 KB Output is correct
6 Correct 553 ms 114900 KB Output is correct
7 Correct 559 ms 121336 KB Output is correct
8 Correct 552 ms 103160 KB Output is correct
9 Correct 558 ms 102904 KB Output is correct
10 Correct 539 ms 84600 KB Output is correct
11 Correct 541 ms 97788 KB Output is correct
12 Correct 548 ms 121464 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 114424 KB Output is correct
2 Correct 539 ms 113656 KB Output is correct
3 Correct 547 ms 113656 KB Output is correct
4 Correct 551 ms 114868 KB Output is correct
5 Incorrect 809 ms 121712 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 86520 KB Output is correct
2 Correct 528 ms 91896 KB Output is correct
3 Correct 524 ms 96504 KB Output is correct
4 Correct 546 ms 121276 KB Output is correct
5 Correct 547 ms 121208 KB Output is correct
6 Correct 553 ms 114900 KB Output is correct
7 Correct 559 ms 121336 KB Output is correct
8 Correct 552 ms 103160 KB Output is correct
9 Correct 558 ms 102904 KB Output is correct
10 Correct 539 ms 84600 KB Output is correct
11 Correct 541 ms 97788 KB Output is correct
12 Correct 548 ms 121464 KB Output is correct
13 Correct 535 ms 114424 KB Output is correct
14 Correct 539 ms 113656 KB Output is correct
15 Correct 547 ms 113656 KB Output is correct
16 Correct 551 ms 114868 KB Output is correct
17 Incorrect 809 ms 121712 KB Output isn't correct
18 Halted 0 ms 0 KB -