SRM 357 500pt : WebsiteRank

問題概要

ノード数N(<2500)以下の有向グラフが与えられる。各ノードは票数1をあらかじめ持っており、相互に到達可能でない、自ノードへの辺を持つノードの票数をさらに加える。あるノードの票数を求める問題。

解法

問題が分かってしまえば、O(N*N)のメモ化解法が素直に実装できる。強連結成分分解も必要そうだけど実はいらない。この問題では、ノード数が2500以下というのを50以下と勘違いしたせいでTLEやら範囲外アクセスやらで落ちまくった。

#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <cstdio>
using namespace std;

typedef long long int64;

const int MAX_N = 3000;

vector< vector<bool> > G;
vector< vector<int> > es, rev_es;
int64 memo[MAX_N];
int N;

struct WebsiteRank {

	int64 countVotes(vector <string> votes, string website) {
		map<string, int> table;
		for(int i=0; i<(int)votes.size(); i++){
			stringstream ss(votes[i]);
			string t;
			while(ss >> t){
				if(table.find(t) == table.end()){
					table[t] = N++;
				}
			}
		}

		G = vector<vector<bool> >(N, vector<bool>(N, false));
		es = vector< vector<int> >(N);
		rev_es = vector<vector<int> >(N);
		for(int i=0; i<(int)votes.size(); i++){
			stringstream ss(votes[i]);
			string t;
			ss >> t;
			int k = table[t];
			while(ss >> t){
				es[table[t]].push_back(k);
				rev_es[k].push_back(table[t]);
			}
		}

		for(int i=0; i<N; i++){
			dfs(i,i);
		}

		return rec(table[website]);
	}


	int64 rec(int v){
		if(memo[v]) return memo[v];
		memo[v] = 1;
		for(int i=0; i<(int)rev_es[v].size(); i++)if(G[rev_es[v][i]][v] && !G[v][rev_es[v][i]]){
			memo[v] += rec(rev_es[v][i]);
		}
		return memo[v];
	}

	void dfs(int v, int u){
		G[v][u] = true;
		for(int i=0; i<(int)es[u].size(); i++)if(!G[v][es[u][i]]){
			dfs(v, es[u][i]);
		}
	}
};