Codeforces ラウンド #277.5 (ディビジョン 2)-D_html/css_WEB-ITnose

質問: ひし形の数を求めてください。両端の点を直接列挙し、隣接リストを使用して、任意の 2 つの中間ノードと両端を選択して形成できるひし形の数を計算します。は r*(r-1)/ 2.

コード:

rreee

D.存在に関する有能な論争

テストごとの制限時間

1 2 番目の

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

トマシュは、バーランドの通りを歩いている間、ずっとさまよって道に迷ってしまいます。びっくり！彼の故郷では、どの交差点であっても、一方の交差点からもう一方の交差点まで歩く方法が 1 つだけあります。ベルラントの首都はまったく異なります!

トマシュは、単純な曖昧さの場合でも混乱することに気づきました。彼は 4 つの異なる交差 a 、 b 、 c 、 d のグループを見て、 a から c への 2 つのパスが存在することを確認します。 1 つは b を経由し、もう 1 つは d を経由します。 このグループを「ペア」と呼ぶことに注意してください。 (a,?b)、(b、?c)、(a,?d)、(d,?c) は、概略的には、下の図に示されているような菱形になります。どの交差点間の道路もトマシュにとって菱形を魅力的にするものではないので、4 つの交差点は彼にとって「いまいましい菱形」のままです

ベルラントの首都には n 個の交差点と m 個の道路があり、すべての道路が一方通行であることを考えると。と が事前にわかっている場合は、市内にある「くそひし形」の数を調べてください。

ひし形を比較するとき、交点 b と d の順序は関係ありません。

入力

入力の 1 行目整数のペア n、m (1?≤?n?≤?3000、?0?≤?m?≤?30000) ? 次の m 行には、1 行に 1 つずつ道路がリストされます。それぞれの道路は、整数 ai,?bi (1?≤?ai,?bi?≤?n;ai?≠?bi) で与えられます。交差点のペアの間には、2 つの方向のそれぞれに最大で 1 本の道路があります。

ある交差点から他の交差点に到達できるという保証はありません。

出力

印刷必要な数の「くそーな菱形」

サンプルテスト

入力

#include<iostream>#include<cstdio>#include<cmath>#include<map>#include<cstring>#include<algorithm>#define rep(i,a,b) for(int i=(a);i<(b);i++)#define rev(i,a,b) for(int i=(a);i>=(b);i--)#define clr(a,x) memset(a,x,sizeof a)typedef long long LL;using namespace std;const int mod=1e9 +7;const int maxn=3005;const int maxm=30005;int first[maxn],nex[maxm],v[maxm],ecnt,g[maxn][maxn];void add_(int a,int b){    v[ecnt]=b;    nex[ecnt]=first[a];    first[a]=ecnt++;}int main(){    int n,m,x,y;    while(~scanf("%d%d",&n,&m))    {        memset(first,-1,sizeof first);ecnt=0;        memset(g,0,sizeof g);        for(int i=0;i<m;i++)            scanf("%d%d",&x,&y),add_(x,y),g[x][y]=1;        int ans=0;        for(int i=1;i<=n;i++)        {           for(int j=1;j<=n;j++)           if(i!=j){               int r=0;               for(int e=first[i];~e;e=nex[e])               if(g[v[e]][j])r++;               ans+=r*(r-1)/2;           }        }        printf("%d\n",ans);    }    return 0;}

入力

5 41 22 31 44 3

出力 rree