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
AC × 3
AC × 39
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