Submission #145448

#	Time	Username	Problem	Language	Result	Execution time	Memory
145448		luciocf	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	244 ms	19192 KiB

uzastopni

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10;
const int maxv = 110;

int a[maxn];

bool tem[maxv][maxv];

vector<int> grafo[maxn];

bitset<maxv> bs[maxn][maxv];

void undo(void)
{
	for (int i = 1; i < maxv; i++)
		for (int j = 1; j < maxv; j++)
			tem[i][j] = 0;
}

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

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

		for (int i = 1; i < maxv; i++)
		{
			for (int j = i; j < maxv; j++)
			{
				if (i > a[u] && i <= a[v] && bs[v][i][j]) bs[u][i][j] = 1;
				if (i <= a[v] && bs[v][i][j]) tem[i][j] = 1;
			}
		}
	}

	bs[u][a[u]][a[u]] = tem[a[u]][a[u]] = 1;

	for (int l = maxv-1; l > a[u]; l--)
		for (int r = l; r < maxv-1; r++)
			if (tem[l][r])
				bs[u][l] |= bs[u][r+1];

	bs[u][a[u]] |= bs[u][a[u]+1];

	for (int l = a[u]-1; l >= 1; l--)
		for (int r = l; r < a[u]; r++)
			if (tem[l][r])
				bs[u][l] |= bs[u][r+1]; 
}

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

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	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);
	}

	dfs(1, 0);

	int ans = 0;
	for (int i = 1; i <= a[1]; i++)
		ans += (int)bs[1][i].count();

	printf("%d\n", ans);
}

Compilation message (stderr)

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
uzastopni.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
uzastopni.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160