Submission #110420

#	Time	Username	Problem	Language	Result	Execution time	Memory
110420		luciocf	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	239 ms	16428 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

int d[2][maxn], qtd[2][maxn];

int ans[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs(v, u);

		if (d[0][v]+1 > d[0][u])
			d[1][u] = d[0][u], d[0][u] = d[0][v]+1;
		else if (d[0][v]+1 > d[1][u])
			d[1][u] = d[0][v]+1;
	}

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		if (d[0][v]+1 == d[0][u])
			qtd[0][u] += qtd[0][v];
		if (d[0][v]+1 == d[1][u])
			qtd[1][u] += qtd[0][v];
	}

	if (grafo[u].size() == 1 && u != 1)
		qtd[0][u] = 1;

	if (d[1][u] == 0)
		qtd[1][u] = 1;
}

void rotate(int u, int p)
{
	if (qtd[0][u] == 1)
		ans[u] = 1;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		int ant[2] = {d[0][u], qtd[0][u]};

		if (d[0][v]+1 == d[0][u])
		{
			d[0][u] = d[1][u], qtd[0][u] = qtd[1][u];

			if (d[0][v]+1 == d[0][u])
				qtd[0][u] -= qtd[0][v];
		}

		qtd[0][v] = qtd[1][v] = 0;

		if (d[0][u]+1 > d[0][v])
			d[1][v] = d[0][v], d[0][v] = d[0][u]+1;
		else if (d[0][u]+1 > d[1][v])
			d[1][v] = d[0][u]+1;

		for (auto w: grafo[v])
		{
			if (d[0][w]+1 == d[0][v])
				qtd[0][v] += qtd[0][w];
			if (d[0][w]+1 == d[1][v])
				qtd[1][v] += qtd[0][w];
		}

		rotate(v, u);

		d[0][u] = ant[0], qtd[0][u] = ant[1];
	}
}

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	for (int i = 1; i <= m; i++)
	{
		int fodase;
		scanf("%d", &fodase);
	}

	dfs(1, 0);
	rotate(1, 0);

	for (int i = 1; i <= n; i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &fodase);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32