oj.uz

Submission #250375

# Submission time Handle Problem Language Result Execution time Memory
250375 2020-07-17T16:03:42 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 1000 ms 117944 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++;
	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])
		{
			cikl.push_back(j + ((d[i] - d[j] + s) << 20));
		}
	}
	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])
		{
			if (binary_search(cikl.begin(), cikl.end(), v + (c << 20)))
				return true;
			if (binary_search(cikl.begin(), cikl.end(), v + ((ilg / c) << 20)))
				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 519 ms 84728 KB Output is correct
2 Correct 521 ms 84728 KB Output is correct
3 Correct 527 ms 84728 KB Output is correct
4 Correct 543 ms 86088 KB Output is correct
5 Correct 564 ms 85240 KB Output is correct
6 Correct 513 ms 84728 KB Output is correct
7 Correct 556 ms 85816 KB Output is correct
8 Correct 576 ms 84740 KB Output is correct
9 Correct 523 ms 84728 KB Output is correct
10 Correct 568 ms 84728 KB Output is correct
11 Correct 526 ms 84728 KB Output is correct
12 Correct 571 ms 85744 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 85112 KB Output is correct
2 Correct 538 ms 84984 KB Output is correct
3 Correct 551 ms 84768 KB Output is correct
4 Correct 540 ms 84984 KB Output is correct
5 Execution timed out 1085 ms 117944 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 84728 KB Output is correct
2 Correct 521 ms 84728 KB Output is correct
3 Correct 527 ms 84728 KB Output is correct
4 Correct 543 ms 86088 KB Output is correct
5 Correct 564 ms 85240 KB Output is correct
6 Correct 513 ms 84728 KB Output is correct
7 Correct 556 ms 85816 KB Output is correct
8 Correct 576 ms 84740 KB Output is correct
9 Correct 523 ms 84728 KB Output is correct
10 Correct 568 ms 84728 KB Output is correct
11 Correct 526 ms 84728 KB Output is correct
12 Correct 571 ms 85744 KB Output is correct
13 Correct 537 ms 85112 KB Output is correct
14 Correct 538 ms 84984 KB Output is correct
15 Correct 551 ms 84768 KB Output is correct
16 Correct 540 ms 84984 KB Output is correct
17 Execution timed out 1085 ms 117944 KB Time limit exceeded
18 Halted 0 ms 0 KB -