Codeforces #277.5 Div2 D. Unbearable Controversy of Being

CからDで難易度上昇。
http://codeforces.com/contest/489/problem/D

問題

N頂点M有向辺からなるグラフが与えられる。

ある頂点群は菱形を成すとは、異なる頂点a,b,c,dの組において、a→b、a→d、b→c、d→cとなる場合を示す(bとdは逆でも１つと数える)

グラフにおける菱形の数を答えよ。

解法

愚直に行おうとするとO(N^3)やO(N^4)かかるので、もう少し短くする必要がある。
色々方法はありそうだが、自分の解法を紹介。

まず各頂点における隣接点をvectorで格納し、ソートしておく。
また逆向きの辺についても同様にvectorで格納し、ソートしておく。

次にb,dの候補を総当たりする。
b,dについて、それぞれの隣接点となるvectorについて、set_intersectionを用いて共通部分を求めることで、cの候補を求める。
同様に、それぞれの逆向きの隣接点となるvectorについて、set_intersectionを用いて共通部分を求めることで、aの候補を求める。
あとは(aの候補数)*(cの候補数)を累積していく…と言いたいが、aとcが同じ頂点の可能性があり、答えに余分に足しこんでいるかもしれない。
そこでaの候補とcの候補で再度共通部分を求め、その数の分だけは引いておくと良い。

本番これ計算量自信なかったんだけど通った。O(N*M)で済んでるのかな…。

int N,M;
vector<int> E[4000];
vector<int> R[4000];

int mask[3001][105];
int mat[3001][3001];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		R[y-1].push_back(x-1);
	}
	FOR(i,N) sort(E[i].begin(),E[i].end());
	FOR(i,N) sort(R[i].begin(),R[i].end());
	
	ll ret=0;
	FOR(x,N) for(y=x+1;y<N;y++) {
		vector<int> A,B,C;
		set_intersection(E[x].begin(),E[x].end(),E[y].begin(),E[y].end(),inserter(A,A.begin()));
		if(A.empty()) continue;
		set_intersection(R[x].begin(),R[x].end(),R[y].begin(),R[y].end(),inserter(B,B.begin()));
		if(B.empty()) continue;
		set_intersection(A.begin(),A.end(),B.begin(),B.end(),inserter(C,C.begin()));
		ret += A.size()*B.size()-C.size();
	}
	cout<<ret<<endl;
}

まとめ

通って自分でびっくり。