Cod sursa(job #919392)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:05:37
Problema Trigame Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 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;
}