oj.uz

답안 #250373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250373 2020-07-17T16:00:36 Z tutis File Paths (BOI15_fil) C++17
33 / 100
 862 ms 87952 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;
	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<ll, bool>cikl;
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			cikl[j + ((d[i] - d[j] + s) << 10)] = true;
		}
	}
	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 (D.find(ilg - s) != D.end())
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (ll c : dal[ilg])
		{
			if (cikl.find(v + (c << 10)) != cikl.end())
				return true;
			if (cikl.find(v + ((ilg / c) << 10)) != cikl.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

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 84856 KB Output is correct
2 Correct 629 ms 84856 KB Output is correct
3 Correct 641 ms 84856 KB Output is correct
4 Correct 656 ms 87800 KB Output is correct
5 Correct 770 ms 85568 KB Output is correct
6 Correct 813 ms 84984 KB Output is correct
7 Correct 862 ms 87952 KB Output is correct
8 Correct 631 ms 84856 KB Output is correct
9 Correct 652 ms 84868 KB Output is correct
10 Correct 679 ms 84728 KB Output is correct
11 Correct 808 ms 84728 KB Output is correct
12 Correct 829 ms 87936 KB Output is correct

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 835 ms 84984 KB Output is correct
2 Correct 705 ms 85112 KB Output is correct
3 Incorrect 706 ms 85116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 84856 KB Output is correct
2 Correct 629 ms 84856 KB Output is correct
3 Correct 641 ms 84856 KB Output is correct
4 Correct 656 ms 87800 KB Output is correct
5 Correct 770 ms 85568 KB Output is correct
6 Correct 813 ms 84984 KB Output is correct
7 Correct 862 ms 87952 KB Output is correct
8 Correct 631 ms 84856 KB Output is correct
9 Correct 652 ms 84868 KB Output is correct
10 Correct 679 ms 84728 KB Output is correct
11 Correct 808 ms 84728 KB Output is correct
12 Correct 829 ms 87936 KB Output is correct
13 Correct 835 ms 84984 KB Output is correct
14 Correct 705 ms 85112 KB Output is correct
15 Incorrect 706 ms 85116 KB Output isn't correct
16 Halted 0 ms 0 KB -