| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250278 |
2020-07-17T10:30:20 Z |
tutis |
File Paths (BOI15_fil) |
C++17 |
|
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";
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1018 ms |
119672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
