Witch game

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, deg[MAXN], nxt[MAXN];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	memset(nxt, -1, sizeof(nxt));
	for (int i = 0; i < n; i++){
		cin >> nxt[i], nxt[i]--;
		if (nxt[nxt[i]] != i){
			deg[i]++;
			deg[nxt[i]]++;
		}
	}
	ll cnt = 1ll*n*(n-1)*(n-2)/ 6;
	cnt <<= 1;
	for (int i = 0; i < n; i++)
		cnt -= 1ll*deg[i]*(n-1-deg[i]);
	cnt >>= 1;

	cnt *= 3ll;
	for (int i = 0; i < n; i++)
		if (nxt[i] != i && nxt[nxt[i]] != i && nxt[nxt[nxt[i]]] == i)	cnt--;

	cnt /= 3ll;
	cout << cnt << endl;
	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED