cjb-poi2010teleportation

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
#define C(n) (1ll*n*(n-1)/2)
using namespace std;
vector<int> g[41000];
int n,m;
long long ans;
int A,B,C,D;
int col[41000];
int main()
{
    cin>>n>>m;
    rep(i,n)g[i].clear();
    rep(i,m){ int x,y; scanf("%d%d",&x,&y); g[x].pb(y); g[y].pb(x); }
    A=B=C=D=0;
    col[1]=1;  col[2]=6;
    A=g[1].size(); for(auto p:g[1])col[p]=2;
    D=g[2].size(); for(auto p:g[2])col[p]=5;
    rep(i,n)if (col[i]==2)for(auto p:g[i])if (!col[p])col[p]=3,B++;
    rep(i,n)if (col[i]==5)for(auto p:g[i])if (!col[p])col[p]=4,C++;
    int cnt=0; rep(i,n)if (!col[i])col[i]=(A>D)?3:4,cnt++; 
    if (A>D)B+=cnt; else C+=cnt; 
    ans=C(A)+C(B)+C(C)+C(D)+A+1ll*A*B+1ll*B*C+1ll*C*D+D-m;
    cout<<ans<<endl;
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
#define C(n) (1ll*n*(n-1)/2)
using namespace std;
vector<int> g[41000];
int n,m;
long long ans;
int A,B,C,D;
int col[41000];
int main()
{
    cin>>n>>m;
    rep(i,n)g[i].clear();
    rep(i,m){ int x,y; scanf("%d%d",&x,&y); g[x].pb(y); g[y].pb(x); }
    A=B=C=D=0;
    col[1]=1;  col[2]=6;
    A=g[1].size(); for(auto p:g[1])col[p]=2;
    D=g[2].size(); for(auto p:g[2])col[p]=5;
    rep(i,n)if (col[i]==2)for(auto p:g[i])if (!col[p])col[p]=3,B++;
    rep(i,n)if (col[i]==5)for(auto p:g[i])if (!col[p])col[p]=4,C++;
    int cnt=0; rep(i,n)if (!col[i])col[i]=(A>D)?3:4,cnt++; 
    if (A>D)B+=cnt; else C+=cnt; 
    ans=C(A)+C(B)+C(C)+C(D)+A+1ll*A*B+1ll*B*C+1ll*C*D+D-m;
    cout<<ans<<endl;
    return 0;
}