cafelier@SRM

Codeforces 109 Div1 C

あとで | 13:58 |

• ハッシュしなくても漸近計算量は O(N log N) ではあると思うんですよ、と思って
• 2970ms! （不毛な努力）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;

int main()
{
   // Input ------------------------------------------------------
   int V,E; scanf("%d%d",&V,&E);

   vector<pair<int,int>> edges(E); // edges
   vector<vector<int>>   ne(V);    // neighborhood of each node
   int                   deg0 = V; // number of degree-0 nodes

   for(auto& e : edges)
   {
      int a,b; scanf("%d%d",&a,&b); --a, --b;
      e = make_pair(a,b);
      if(ne[a].empty()) --deg0;
      if(ne[b].empty()) --deg0;
      ne[a].push_back(b);
      ne[b].push_back(a);
   }
   for(auto& n : ne)
      sort(n.begin(), n.end());

   // Solve -------------------------------------------------------
   LL total = 0;

   auto sorted_ne = ne;
   sort(sorted_ne.begin(), sorted_ne.end());
   for(int i=0; i<V; ) {
      int k=i+1;
      while( k<V && sorted_ne[i]==sorted_ne[k] )
         ++k;
      total += LL(k-i)*(k-i-1)/2;
      i = k;
   }

   for(int i=0; i<V; ++i)
      ne[i].insert(lower_bound(ne[i].begin(), ne[i].end(), i), i);

   if( V-deg0 < 10000 ) { // may be dense
      sort(ne.begin(), ne.end());
      for(int i=0; i<V; ) {
         int k=i+1;
         while( k<V && ne[i]==ne[k] )
            ++k;
         total += LL(k-i)*(k-i-1)/2;
         i = k;
      }
   }
   else // sparse
      for(auto e : edges)
         if( ne[e.first] == ne[e.second] )
            ++total;

   // Output -------------------------------------------------------
   cout << total << endl;
}