G - Triangle Editorial by rui_er


We can enumerate \(1\le i < j\le n\) such that there is an edge between \((i,j)\), then we count \(k:j < k\le n\) such that there is an edge between \((j,k)\) and \((i,k)\). This can be done in \(\mathcal O(n^3)\).

We can use bitset to optimize it to \(\mathcal O(\frac{n^3}{\omega})\), \(\omega=64\).

Submission

posted:
last update: