#include <stdio.h>
#include <vector>
#include <algorithm>
typedef struct edge edge;
struct edge
{
int v, w;
};
std::vector<edge> AdjList[3005];
std::vector<int> QS[3005];
int Pa[3005], Sum[3005];
void dfs(int u, int pa, int sum)
{
// printf("dfs %d %d %d\n", u, pa, sum);
int i, j, v, s = AdjList[u].size();
Pa[u] = pa;
if (pa != -1)
QS[u] = QS[pa];
QS[u].push_back(sum);
Sum[u] = sum;
for (i = 0; i < s; i++)
{
v = AdjList[u][i].v;
if (v != pa)
{
dfs(v, u, sum + AdjList[u][i].w);
for (j = 0; j < QS[v].size(); j++)
QS[u].push_back(QS[v][j]);
}
}
}
std::vector<int> F[1000005];
int main()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
k--;
int i, j, r, kk;
F[1].push_back(1);
// kk = 0;
for (i = 2; i <= k; i++)
{
r = i;
for (j = 2; j*j <= i; j++)
{
if (i%j == 0)
{
r /= j;
break;
}
}
if (j*j > i)
{
F[i].push_back(1);
F[i].push_back(i);
}
else
{
F[i] = F[r];
for (kk = 0; kk < F[r].size(); kk++)
{
F[i].push_back(F[r][kk]*j);
}
std::sort(F[i].begin(), F[i].end());
F[i].resize(std::unique(F[i].begin(), F[i].end()) - F[i].begin());
}
// if (F[i].size() > kk)
// kk = F[i].size();
// printf("%d = %d\n", i, F[i].size());
}
// printf("%d\n", kk);
int s;
scanf("%d", &s);
s++;
int pa, w;
for (i = 1; i <= n; i++)
{
scanf("%d %d", &pa, &w);
AdjList[i].push_back({pa, w + 1});
AdjList[pa].push_back({i, w + 1});
}
dfs(0, -1, 0);
for (i = 0; i <= n; i++)
{
// printf("%d: ", i);
std::sort(QS[i].begin(), QS[i].end());
QS[i].resize(std::unique(QS[i].begin(), QS[i].end()) - QS[i].begin());
// for (j = 0; j < QS[i].size(); j++)
// printf("%d ", QS[i][j]);
// printf("\n");
}
int l, p, q;
int mark;
for (i = 0; i < m; i++)
{
scanf("%d %d", &pa, &l);
kk = k - l - Sum[pa];
mark = 0;
// printf("kk%d\n", kk);
if (kk == 0)
{
printf("YES\n");
continue;
}
while (pa != -1)
{
for (j = 0; j < F[kk].size(); j++)
{
r = kk/F[kk][j] - s;
// if (r < 0) break;
// printf("r%d\n", r);
if (F[kk][j] == 1)
{
//special case
q = std::lower_bound(QS[0].begin(), QS[0].end(), Sum[pa] + r) - QS[0].begin();
if (q < QS[0].size() && QS[0][q] == Sum[pa] + r)
{
printf("YES\n");
mark = 1;
break;
}
}
q = std::lower_bound(QS[pa].begin(), QS[pa].end(), Sum[pa] + r) - QS[pa].begin();
if (q < QS[pa].size() && QS[pa][q] == Sum[pa] + r)
{
printf("YES\n");
mark = 1;
break;
}
}
if (mark)
break;
pa = Pa[pa];
}
if (!mark)
printf("NO\n");
}
}
Compilation message
fil.cpp: In function 'void dfs(int, int, int)':
fil.cpp:27:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < QS[v].size(); j++)
~~^~~~~~~~~~~~~~
fil.cpp: In function 'int main()':
fil.cpp:60:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (kk = 0; kk < F[r].size(); kk++)
~~~^~~~~~~~~~~~~
fil.cpp:107:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < F[kk].size(); j++)
~~^~~~~~~~~~~~~~
fil.cpp:116:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (q < QS[0].size() && QS[0][q] == Sum[pa] + r)
~~^~~~~~~~~~~~~~
fil.cpp:124:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (q < QS[pa].size() && QS[pa][q] == Sum[pa] + r)
~~^~~~~~~~~~~~~~~
fil.cpp:92:12: warning: unused variable 'p' [-Wunused-variable]
int l, p, q;
^
fil.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &s);
~~~~~^~~~~~~~~~
fil.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &pa, &w);
~~~~~^~~~~~~~~~~~~~~~~~
fil.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &pa, &l);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1107 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1112 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1107 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
