Cod sursa(job #607188)

Utilizator crushackPopescu Silviu crushack Data 10 august 2011 23:42:43
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <vector>
#define NMax 5000
using namespace std;

const char IN[]="triplete.in",OUT[]="triplete.out";

struct muchie{
    int x,y;
} m[NMax*NMax];

int N,M,Rez;
int ad[NMax][NMax/31];

void set(int x,int y,int v=1){
    ad[x][y/31]+= v ? (1<<(y%31)) : -(1<<(y%31));
}

int count(int x){
    int ret=0;
    while (x) x=x&(x-1),++ret;
    return ret;
}

int main()
{
    int i,j,x,y;
    freopen(IN,"r",stdin);
    scanf("%d%d",&N,&M);
    for (i=0;i<M;++i)
    {
        scanf("%d%d",&x,&y);
        set(x,y);
        set(y,x);
        m[i].x=x;m[i].y=y;
    }

    for (i=0;i<M;++i)
    {
        set(m[i].x,m[i].y,0);
        set(m[i].y,m[i].x,0);
        for (j=0;j<=N/31;++j)
            Rez+=count(ad[m[i].x][j]&ad[m[i].y][j]);
        set(m[i].x,m[i].y);
        set(m[i].y,m[i].x);
    }

    freopen(OUT,"w",stdout);
    printf("%d\n",Rez/3);
    fclose(stdout);

    return 0;
}