oj.uz

답안 #250278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250278 2020-07-17T10:30:20 Z tutis File Paths (BOI15_fil) C++17
0 / 100
 1000 ms 119928 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>
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);
			dal[j].push_back(j / i);
		}
	int n, m, k, s;
	cin >> n >> m >> k >> s;
	s++;
	int 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]);
	}
	sort(D.begin(), D.end());
	vector<int>cikl[n + 1];
	for (int i = 0; i <= n; i++)
	{
		for (int j = i; j != -1; j = p[j])
		{
			cikl[j].push_back(d[i] - d[j] + s);
		}
	}
	for (int i = 0; i <= n; i++)
		sort(cikl[i].begin(), cikl[i].end());
	function<bool(int, int)>ok = [&](int v, int 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 (binary_search(D.begin(), D.end(), ilg - s))
			return true;
		if (ilg <= d[v] + s)
			return false;
		ilg -= d[v];
		for (int c : dal[ilg])
		{
			if (binary_search(cikl[v].begin(), cikl[v].end(), c))
				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
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 747 ms 119288 KB Output is correct
2 Correct 746 ms 119416 KB Output is correct
3 Correct 771 ms 119384 KB Output is correct
4 Correct 749 ms 119800 KB Output is correct
5 Correct 953 ms 119528 KB Output is correct
6 Correct 895 ms 119416 KB Output is correct
7 Correct 763 ms 119928 KB Output is correct
8 Correct 751 ms 119416 KB Output is correct
9 Correct 749 ms 119416 KB Output is correct
10 Correct 937 ms 119440 KB Output is correct
11 Correct 891 ms 119544 KB Output is correct
12 Execution timed out 1047 ms 119800 KB Time limit exceeded

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1018 ms 119672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 747 ms 119288 KB Output is correct
2 Correct 746 ms 119416 KB Output is correct
3 Correct 771 ms 119384 KB Output is correct
4 Correct 749 ms 119800 KB Output is correct
5 Correct 953 ms 119528 KB Output is correct
6 Correct 895 ms 119416 KB Output is correct
7 Correct 763 ms 119928 KB Output is correct
8 Correct 751 ms 119416 KB Output is correct
9 Correct 749 ms 119416 KB Output is correct
10 Correct 937 ms 119440 KB Output is correct
11 Correct 891 ms 119544 KB Output is correct
12 Execution timed out 1047 ms 119800 KB Time limit exceeded