K (Zaoch 2011-2012)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

#define pb push_back
#define N 5005

using namespace std;

vector<int> graph[N], num[N], edge[N];
bool g[N][N], was[N], used[N][N];
int same[N][N], in_distance_2[N], twice[N][N];

typedef long long LL;

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int r1, r2;
        cin >> r1 >> r2;

        graph[r1].pb(r2);
        graph[r2].pb(r1);
        num[r1].pb(i);
        num[r2].pb(i);
        g[r1][r2] = g[r2][r1] = 1;
    }

    LL res = n;
    res += n * (n - 1) / 2 - m;

    LL subres = 0, subres2 = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < graph[i].size(); j++) {
            int to = graph[i][j];
            for (int k = 0; k < graph[to].size(); k++) {
                int to2 = graph[to][k];
                if (to2 != i) {
                    if (!used[ num[to][k] ][i]) {
                        in_distance_2[i]++;
                        edge[ num[to][k] ].pb(i);
                        used[ num[to][k] ][i] = true;
                    }
                }
            }
        }

    memset(was, false, sizeof(was));

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < graph[i].size(); j++) {
            int to = graph[i][j];
            for (int k = 0; k < graph[to].size(); k++) {
                int v1 = i, v2 = graph[to][k];
                twice[v1][v2]++;
            }
        }


    for (int i = 0; i < m; i++)
        for (int j = 0; j < edge[i].size(); j++)
            for (int k = j + 1; k < edge[i].size(); k++) {
                int v1 = edge[i][j], v2 = edge[i][k];
                same[v1][v2]++;
                same[v2][v1]++;
            }

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            if (!g[i][j]) {
                int cnt = 2;
                for (int k = 0; k < graph[i].size(); k++) {
                    int to = graph[i][k];
                    was[to] = true;
                    cnt++;
                }
                for (int k = 0; k < graph[j].size(); k++) {
                    int to = graph[j][k];
                    if (!was[to])
                        cnt++;
                }
                if (n - cnt > 1) {
                    subres += (n - cnt) * (n - cnt - 1) / 2 - (m - int(graph[i].size()) - int(graph[j].size()) - in_distance_2[i] - in_distance_2[j] + twice[i][j] + twice[j][i] + same[i][j]);
                }
                subres2 += n - cnt;

                for (int k = 0; k < graph[i].size(); k++) {
                    int to = graph[i][k];
                    was[to] = false;
                }
            }
        }

    res += subres / 6 + subres2 / 3;
    cout << res << endl;

    return 0;
}