[agc006F]Blackout

Description

传送门

Solution

这道题的操作是真的得服气。。感谢各位大佬的指导。

首先我们看看答案的最大值:10¹⁰。哦不，这不可能存在，我们肯定不可能一轮轮枚举点进行扩展的。

所以，接下来我们进入正题：

由于我们不可能计算出所有具体的点，我们肯定得依靠某种玄学秘法来表示原本的点（不然你没法往下推啊qaq），然后通过神秘手段来搞事情。

em我们把一个点(x,y)看做是一条x->y的有向边。如果有x->y,y->z,则我们可以加上边z->x。

这些点将构成若干联通块，我们对其进行染色。

我们一共染3种色0,1,2。如果有x->y，则y的颜色为(x的颜色+1)%3。

对于某个联通块，有3种情况。

1，一共只用了两种颜色并且没有一个点被染了两种色，我们可以形象地理解为该图只有两层，但是我们需要3层才可以额外加边，答案不变。

2，一共刚好用了3色并且没有一个点被染了两种色，则2色的可以连向0色，0色的可以连向1色，1色的可以连向2色，统计加了多少边就好。

3，有一个点被染了两种色，图中出现环。环中任意两点x,y将会存在x->y,y->x。然后可证明，这时如果往这个环外多加一个点，在操作完成后也会满足任意两点x,y有x->y,y->x。即该联通块的边总数为点数的平方。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,x,y;
struct node{int y,nxt,t;
}g[1000010];int h[100010],tot=0;
int cnt[3],col[100010],_point,_link;
bool vis[100010],_is;
void dfs(int x)
{
    cnt[col[x]]++;vis[x]=1;_point++;
    for(int i=h[x];i;i=g[i].nxt)
    {
        _link+=(g[i].t==1);
        if (!vis[g[i].y]) col[g[i].y]=(col[x]+g[i].t+3)%3,dfs(g[i].y);
        else if (col[g[i].y]!=(col[x]+g[i].t+3)%3) _is=0;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g[++tot]=node{y,h[x],1};h[x]=tot;
        g[++tot]=node{x,h[y],-1};h[y]=tot;
    }
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        _is=1;_point=_link=0;cnt[0]=cnt[1]=cnt[2]=0;
        dfs(i);
        if (!_is) ans+=1ll*_point*_point;
        else if (cnt[0]&&cnt[1]&&cnt[2]) ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
        else ans+=_link;
    }
    printf("%lld",ans);
    
}