Cod sursa(job #1166239)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 aprilie 2014 13:12:46
Problema Triplete Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 4150;

int N, M, sol;
int B[MAX_N][MAX_N / 30];
vector < int > v[MAX_N];
bool A[MAX_N][MAX_N];

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

    f >> N >> M;
    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;

        v[x].push_back(y);
        A[x][y] = A[y][x] = 1;
    }

    int m = N + 30 - (N % 30);

    for(int i = 1; i <= N; ++i) {
        for(int k = 1; k * 30 <= m; ++k) {
            for(int j = (k - 1) * 30 + 1, h = 0; j <= k * 30; ++j, ++h)
                B[i][k] ^= (A[i][j] << h);
        }
    }

    for(int i = 1; i <= N; ++i)
        for(int j = 0; j < (int) v[i].size(); ++j) {
            int x = i, y = v[i][j];

            for(int k = 1; k * 30 <= m; ++k) {
                int temp = B[x][k] & B[y][k];
                while(temp) {
                    sol += temp % 2;
                    temp /= 2;
                }
            }
        }
    sol /= 3;

    g << sol << "\n";

    f.close();
    g.close();

    return 0;
}