Cod sursa(job #2051812)

Utilizator akaprosAna Kapros akapros Data 29 octombrie 2017 16:18:40
Problema Trigame Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <bits/stdc++.h>
#define maxN 2050
using namespace std;

FILE *fin = freopen("trigrame.in", "r", stdin);
FILE *fout = freopen("trigrame.out", "w", stdout);

/* ---------------------------------- */
int n;
vector < int > V[maxN];
/* ---------------------------------- */
int f[maxN], lev[maxN], down[2][maxN], maxDown[maxN];
bool vis[maxN][maxN], dp[maxN][maxN];

int ans;

void dfs1(int nod)
{
    down[0][nod] = down[1][nod] = 1;
    for (int son : V[nod])
        if (!f[son])
        {
            f[son] = nod;
            lev[son] = lev[nod] + 1;
            dfs1(son);
            if (down[0][son] + 1 > down[0][nod])
            {
                down[1][nod] = down[0][nod];
                down[0][nod] = down[0][son] + 1;
            }
            else
                down[1][nod] = max(down[1][nod], down[0][son] + 1);
        }
}
void dfs2(int nod)
{
    int bestNod;
    for (int son : V[nod])
        if (f[son] == 1)
        {
            maxDown[son] = maxDown[nod] + 1;
            if (down[0][nod] == down[0][son] + 1)
            {
                maxDown[son] = max(maxDown[son], down[1][nod] + 1);
                bestNod = down[1][nod];
            }
            else
            {
                maxDown[son] = max(maxDown[son], down[0][nod] + 1);
                bestNod = down[0][nod];
            }
            bestNod = max(bestNod, maxDown[nod]);
            vis[nod][son] = vis[son][nod] = 1;
            if (down[0][son] < bestNod)
            {
                dp[nod][son] = 1;
                dp[son][nod] = 0;
            }
            else if (down[0][son] > bestNod)
            {
                dp[nod][son] = 0;
                dp[son][nod] = 1;
            }
            else
                dp[nod][son] = dp[son][nod] = 0;
        }
}

int Dp(int x, int y)
{
    if (vis[x][y])
        return dp[x][y];
    vis[x][y] = 1;

    for (int z : V[x])
        if (z != y)
        {
            if (!vis[y][z])
                dp[y][z] = Dp(y, z);
            if (!dp[y][z])
            {
                dp[x][y] = 1;
                vis[y][x] = 1;
                dp[y][x] = 0;
                return 1;
            }
        }
    dp[x][y] = 0;
    return 0;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        V[x].push_back(y);
        V[y].push_back(x);
    }
    f[1] = -1;
    dfs1(1);
    maxDown[1] = 1;
    dfs2(1);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            if (j != i)
            {
                if (!vis[i][j])
                    dp[i][j] = Dp(i, j);
                ans += dp[i][j];
                // if (dp[i][j])
                //     printf("%d %d\n", i, j);
            }
    printf("%d\n", ans);
    return 0;
}