Cod sursa(job #1998052)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 6 iulie 2017 13:59:30
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <cstdio>
#include <bitset>
#include <vector>
#include <algorithm>
#define VAL 4105
#define DIM 200005

using namespace std;

int N, M, i, j;
int a, b, cnt;
int AUX[DIM], ANS;
vector <int> v[VAL];
bitset <VAL> ok[VAL];

int main()
{
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
        ok[a][b]=ok[b][a]=1;
    }
    for (i=1; i<=N; i++)
      sort(v[i].begin(), v[i].end());
    for (i=1; i<=N; i++)
    {
        for (j=i+1; j<=N; j++)
        {
            if (ok[i][j]==1)
            {
                a=b=0;
                for (cnt=1; cnt<=v[i].size()+v[j].size(); cnt++)
                {
                    if (a!=v[i].size() && b!=v[j].size())
                    {
                        if (v[i][a]<v[j][b])
                        {
                            AUX[cnt]=v[i][a];
                            a++;
                        }
                        else
                        {
                            AUX[cnt]=v[j][b];
                            b++;
                        }
                    }
                    else
                    {
                        if (a==v[i].size())
                        {
                            AUX[cnt]=v[j][b];
                            b++;
                        }
                        else
                        {
                            AUX[cnt]=v[i][a];
                            a++;
                        }
                    }
                    if (AUX[cnt]==AUX[cnt-1])
                      ANS++;
                }
            }
        }
    }
    printf("%d\n", ANS / 3);
    return 0;
}