Submission #1858480
Source Code Expand
#include <cstdio>
#include <algorithm>
int N, __K__, head[100001], next[199999], to[199999], E, q[100001], fa[100001];
int p[100001], w[100001], g[100001], L[100001], R[100001];
int main()
{
scanf("%d", &N);
for (int i = 1, u, v; i < N; i++)
{
scanf("%d%d", &u, &v);
next[++E] = head[u], to[E] = v, head[u] = E;
next[++E] = head[v], to[E] = u, head[v] = E;
}
for (scanf("%d", &__K__); __K__--; )
{
int x, y;
scanf("%d%d", &x, &y);
p[x] = 1;
w[x] = y;
}
int H = 0, T = 1, u;
q[1] = 1;
while (H < T)
for (int e = head[u = q[++H]]; e; e = next[e])
if (to[e] != fa[u])
fa[q[++T] = to[e]] = u;
for (int i = N; i; i--)
{
int u = q[i];
int appear_0 = 0, L_0 = -1000000000, R_0 = 1000000000;
int appear_1 = 0, L_1 = -1000000000, R_1 = 1000000000;
for (int e = head[u]; e; e = next[e])
if (to[e] != fa[u] && g[to[e]])
{
if (L[to[e]] & 1)
{
appear_1 = 1;
L_1 = std::max(L_1, L[to[e]]);
R_1 = std::min(R_1, R[to[e]]);
}
else
{
appear_0 = 1;
L_0 = std::max(L_0, L[to[e]]);
R_0 = std::min(R_0, R[to[e]]);
}
}
if (appear_0 && appear_1)
{
puts("No");
return 0;
}
if (!appear_0 && !appear_1)
{
if (p[u])
{
g[u] = 1;
L[u] = R[u] = w[u];
}
else
g[u] = 0;
}
else
{
if (appear_0)
{
L[u] = L_0 - 1;
R[u] = R_0 + 1;
}
else
{
L[u] = L_1 - 1;
R[u] = R_1 + 1;
}
if (L[u] > R[u])
{
puts("No");
return 0;
}
if (p[u])
{
if (w[u] < L[u] || w[u] > R[u] || (w[u] ^ L[u]) & 1)
{
puts("No");
return 0;
}
L[u] = R[u] = w[u];
}
g[u] = 1;
}
}
for (int i = 1; i <= N; i++)
{
int u = q[i];
if (p[u])
continue;
if (u == 1)
w[u] = L[u];
else if (!g[u])
w[u] = w[fa[u]] + 1;
else if (L[u] <= w[fa[u]] + 1 && w[fa[u]] + 1 <= R[u])
w[u] = w[fa[u]] + 1;
else
w[u] = w[fa[u]] - 1;
}
puts("Yes");
for (int i = 1; i <= N; i++)
printf("%d\n", w[i]);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Integers on a Tree |
User |
NiroBC |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
2103 Byte |
Status |
AC |
Exec Time |
49 ms |
Memory |
5504 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:7:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:10:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
^
./Main.cpp:14:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (scanf("%d", &__K__); __K__--; )
^
./Main.cpp:17:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
binary_01.txt, binary_02.txt, hand_01.txt, hand_02.txt, hand_03.txt, kary_01.txt, kary_02.txt, kary_03.txt, line_01.txt, line_02.txt, line_03.txt, line_04.txt, line_05.txt, line_06.txt, random0_01.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, random1_08.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random3_01.txt, random3_02.txt, random4_01.txt, random4_02.txt, random4_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt |
Case Name |
Status |
Exec Time |
Memory |
binary_01.txt |
AC |
35 ms |
5504 KB |
binary_02.txt |
AC |
19 ms |
4864 KB |
hand_01.txt |
AC |
1 ms |
2176 KB |
hand_02.txt |
AC |
1 ms |
2176 KB |
hand_03.txt |
AC |
1 ms |
2176 KB |
kary_01.txt |
AC |
18 ms |
3456 KB |
kary_02.txt |
AC |
27 ms |
5376 KB |
kary_03.txt |
AC |
19 ms |
4608 KB |
line_01.txt |
AC |
21 ms |
3712 KB |
line_02.txt |
AC |
27 ms |
4736 KB |
line_03.txt |
AC |
27 ms |
5120 KB |
line_04.txt |
AC |
31 ms |
5504 KB |
line_05.txt |
AC |
19 ms |
3968 KB |
line_06.txt |
AC |
23 ms |
4864 KB |
random0_01.txt |
AC |
28 ms |
3712 KB |
random1_01.txt |
AC |
33 ms |
5504 KB |
random1_02.txt |
AC |
34 ms |
5504 KB |
random1_03.txt |
AC |
35 ms |
5504 KB |
random1_04.txt |
AC |
43 ms |
5504 KB |
random1_05.txt |
AC |
32 ms |
5376 KB |
random1_06.txt |
AC |
32 ms |
5376 KB |
random1_07.txt |
AC |
34 ms |
5504 KB |
random1_08.txt |
AC |
49 ms |
5504 KB |
random2_01.txt |
AC |
23 ms |
4608 KB |
random2_02.txt |
AC |
22 ms |
4608 KB |
random2_03.txt |
AC |
24 ms |
4864 KB |
random2_04.txt |
AC |
21 ms |
4864 KB |
random2_05.txt |
AC |
29 ms |
4864 KB |
random2_06.txt |
AC |
39 ms |
4864 KB |
random3_01.txt |
AC |
21 ms |
4608 KB |
random3_02.txt |
AC |
32 ms |
4864 KB |
random4_01.txt |
AC |
32 ms |
5120 KB |
random4_02.txt |
AC |
32 ms |
5248 KB |
random4_03.txt |
AC |
32 ms |
5504 KB |
sample_01.txt |
AC |
1 ms |
2176 KB |
sample_02.txt |
AC |
1 ms |
2176 KB |
sample_03.txt |
AC |
1 ms |
2176 KB |
star_01.txt |
AC |
35 ms |
5504 KB |
star_02.txt |
AC |
26 ms |
4864 KB |