Cod sursa(job #2455467)

Utilizator victorv88Veltan Victor victorv88 Data 11 septembrie 2019 20:01:36
Problema Triplete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("triplete.in");
ofstream g("triplete.out");

bool graf[4100][4100];

int n, m, a, b, rez, ind_maxi;

vector<pair<int,int>>muchii;

long long buckets[200][200];

void citire()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        f >> a >> b;
        graf[a][b]=graf[b][a]=true;
        muchii.push_back({a,b});
    }
}

void formare_buckets()
{
    int ind=1;
    for (int i=1; i<=n; i++)
    {
        ind=1;
        for (int j=1; j<=n; j+=32, ++ind)
        {
            int adunare=j+32;
            for (int t=j; t<adunare && t<=n; ++t)
            {
                if (graf[i][t])
                {
                    buckets[i][ind]+=(1<<(t-j));
                }
            }
        }
        ind_maxi=ind-1;
    }
}

void adaugare(long long val, int maxi)
{
    for (int i=0; (1<<i)<=val; ++i)
    {
        if ((val&(1<<i)) && i+1>maxi)
            rez++;
    }
}

void rezolvare()
{
    for (auto &v:muchii)
    {
        int n1=v.first;
        int n2=v.second;
        for (int ind=1; ind<=ind_maxi; ++ind)
        {
            adaugare(buckets[n1][ind]&buckets[n2][ind], max(n1,n2));
        }
    }
}

int main()
{
    citire();
    formare_buckets();
    rezolvare();
    g << rez;
    return 0;
}