Cod sursa(job #331577)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 14 iulie 2009 16:22:01
Problema Trigame Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define NMAX 2100
#define max(a, b) ((a) > (b) ? (a) : (b))

int i, j, k, p, q, N, wincnt;
int visited[NMAX], tata[NMAX], special[NMAX], lmax[NMAX], path[NMAX], pathmax[NMAX];
char win[NMAX][NMAX];
vector<int> v[NMAX];

void df1(int x)
{
	int j;

	visited[x] = 1;

	for (j = 0; j < v[x].size(); j++)
		if (!visited[v[x][j]])
		{
			tata[v[x][j]] = x;
			df1(v[x][j]);
		}
}

void df2(int x)
{
	int j;

	visited[x] = 1;

	for (j = 0; j < v[x].size(); j++)
		if (!visited[v[x][j]] && ! special[v[x][j]])
		{
			df2(v[x][j]);
			lmax[x] = max(lmax[x], 1 + lmax[v[x][j]]);
		}
}

void n3sol(void)
{
	int a, b;

	wincnt = 0;

	for (a = 1; a <= N; a++)
		for (b = 1; b <= N; b++)
			if (a != b)
			{
				memset(visited, 0, sizeof(visited));
				memset(tata, 0, sizeof(tata));
				df1(a);

				memset(special, 0, sizeof(special));
				p = b;
				q = 0;
				do
				{
					special[p] = 1;
					q++;
					path[q] = p;
					p = tata[p];
				}
				while (p > 0);

				memset(visited, 0, sizeof(visited));
				memset(lmax, 0, sizeof(lmax));
				for (p = q; p >= 1; p--)
					df2(path[p]);

				pathmax[0] = 0;
				for (p = 1; p <= q; p++)
					pathmax[p] = max(pathmax[p - 1], lmax[path[p]] + p - 1);

				win[a][b] = 0;
				for (p = q; p >= 1 + (q / 2); p--)
					if (lmax[path[p]] + q - p > pathmax[/*q / 2*/ p - 1])
					{
						win[a][b] = 1;
						break;
					}

				// fprintf(stderr, "a=%d, b=%d => %d\n", a, b, win[a][b]);

				if (win[a][b])
					wincnt++;
			}
}

int main()
{
	freopen("trigame.in", "r", stdin);
	
	scanf("%d", &N);
	for (k = 1; k <= N - 1; k++)
	{
		scanf("%d %d", &i, &j);
		v[i].push_back(j);
		v[j].push_back(i);
	}

	n3sol();

	freopen("trigame.out", "w", stdout);
	printf("%d\n", wincnt);

	return 0;
}