Illuminati

// A C++ program for finding
// number of triangles in an
// Undirected Graph. The program
// is for adjacency matrix
// representation of the graph
#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph
constexpr int V = 3000;

//  Utility function for matrix
// multiplication
void multiply(vector<vector<int>>& A, vector<vector<int>>& B,
              vector<vector<int>>& C, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      C[i][j] = 0;
      for (int k = 0; k < n; k++) C[i][j] += A[i][k] * B[k][j];
    }
  }
}

// Utility function to calculate
// trace of a matrix (sum of
// diagonal elements)
int getTrace(vector<vector<int>>& graph, int n) {
  int trace = 0;
  for (int i = 0; i < n; i++) trace += graph[i][i];
  return trace;
}

//  Utility function for calculating
// number of triangles in graph
int triangleInGraph(vector<vector<int>> graph, int n) {
  // To Store graph^2
  vector<vector<int>> aux2(n, vector<int>(n));

  // To Store graph^3
  vector<vector<int>> aux3(n, vector<int>(n));

  //  Initialising aux
  // matrices with 0
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) aux2[i][j] = aux3[i][j] = 0;

  // aux2 is graph^2 now  printMatrix(aux2);
  multiply(graph, graph, aux2, n);

  // after this multiplication aux3 is
  // graph^3 printMatrix(aux3);
  multiply(graph, aux2, aux3, n);

  int trace = getTrace(aux3, n);
  return trace / 6;
}

// driver code
int main() {
  // freopen("d.txt", "r", stdin);
  int n;
  cin >> n;

  vector<vector<int>> adj(n, vector<int>(n));

  for (int i = 0; i < n; i++) {
    string str;
    cin >> str;
    for (int j = 0; j < n; j++) {
      if (str[j] == '1') {
        adj[i][j] = 1;
      } else {
        adj[i][j] = 0;
      }
    }
  }

  cout << triangleInGraph(adj, n) << "\n";
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: TIME LIMIT EXCEEDED

Test 49

Verdict: TIME LIMIT EXCEEDED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED

Test 52

Verdict: TIME LIMIT EXCEEDED

Test 53

Verdict: TIME LIMIT EXCEEDED