提出 #10816297

---

ソースコード 拡げる

#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define MRE assert(0);
const int inf = 1e17;
const int mod =998244353;
typedef pair<int, int> P;
struct edge {
	int to, dir;
};
vector<edge>G[100006];
vector<int>cn[100006];
int a[100006], b[100006];
int d[100006], ced[100006];
int par[100006], siz[100006];
void init(int n) {
	rep(i, n) {
		par[i] = i; siz[i] = 1;
	}
}
int find(int x) {
	if (x == par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y)return;
	if (siz[x] > siz[y])swap(x, y);
	par[x] = y;
	siz[y] += siz[x];
}
void dfs(int now, int label) {
	for (auto e : G[now]) {
		int nl = (label + 3 + e.dir) % 3;
		int nv = e.to;
		if (!(d[nv] & (1 << nl))) {
			d[nv] += (1 << nl);
			dfs(nv, nl);
		}
	}
	return;
}
signed main() {
	int n, m; cin >> n >> m;
	init(n);
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		G[a[i]].push_back({ b[i],1 });
		G[b[i]].push_back({ a[i],-1 });
		unite(a[i], b[i]);
	}
	rep(i, m) {
		ced[find(a[i])]++;
	}
	rep(i, n) {
		if (!d[i]) {
			d[i] = 1;
			dfs(i, 0);
		}
		cn[find(i)].push_back(d[i]);
	}
	int ans = 0;
	
	rep(i, n) {
		vector<int>cnt(8);
		for (int e : cn[i]) {
			rep(j, 8) {
				if ((j&e)==j)cnt[j]++;
			}
		}
		if (!cnt[1] || !cnt[2] || !cnt[4])ans += ced[i];
		else ans+= cnt[1] * cnt[2] + cnt[2] * cnt[4] + cnt[4] * cnt[1] -2* cnt[7] * cnt[7];
		
	}
	cout << ans << endl;
}

提出情報

ジャッジ結果