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]); } } };