2015年1月29日 星期四

2015/01/29 Codeforces 489D. Unbearable Controversy of Being

// http://codeforces.com/contest/489/problem/D
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

int N, M;
vector<int> v[4000];
vector<int> tmp;

typedef vector<int>::iterator vit;

int cnt[4000];

void process(int O, int K)
{
    if( K == 2 )
    {
        cnt[O]++;
        tmp.push_back(O);
    }
    else
    {
        for(int vi = 0; vi < v[O].size(); vi++)
            process(v[O][vi], K+1);
    }
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Mi = 0; Mi < M; Mi++)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        v[a].push_back(b);
    }

    ll Ans = 0;

    for(int Ni = 1; Ni <= N; Ni++)
    {
        process(Ni, 0);

        sort(tmp.begin(), tmp.end());

        vit it = unique(tmp.begin(), tmp.end());
        tmp.resize(it-tmp.begin() );

        for(int ti = 0; ti < tmp.size(); ti++)
        {
            int p = cnt[tmp[ti] ];

            if( tmp[ti] != Ni )
                Ans += (ll)p*(p-1)/2;

            cnt[tmp[ti] ] = 0;
        }

        tmp.clear();
    }

    cout<<Ans<<endl;

}

沒有留言:

張貼留言