8128edf954 2013-12-15 kinaba: #include <iostream> 8128edf954 2013-12-15 kinaba: #include <sstream> 8128edf954 2013-12-15 kinaba: #include <iomanip> 8128edf954 2013-12-15 kinaba: #include <vector> 8128edf954 2013-12-15 kinaba: #include <string> 8128edf954 2013-12-15 kinaba: #include <map> 8128edf954 2013-12-15 kinaba: #include <set> 8128edf954 2013-12-15 kinaba: #include <algorithm> 8128edf954 2013-12-15 kinaba: #include <numeric> 8128edf954 2013-12-15 kinaba: #include <iterator> 8128edf954 2013-12-15 kinaba: #include <functional> 8128edf954 2013-12-15 kinaba: #include <complex> 8128edf954 2013-12-15 kinaba: #include <queue> 8128edf954 2013-12-15 kinaba: #include <stack> 8128edf954 2013-12-15 kinaba: #include <cmath> 8128edf954 2013-12-15 kinaba: #include <cassert> 8128edf954 2013-12-15 kinaba: #include <tuple> 8128edf954 2013-12-15 kinaba: using namespace std; 8128edf954 2013-12-15 kinaba: typedef long long LL; 8128edf954 2013-12-15 kinaba: typedef complex<double> CMP; 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: class TwistyPassages { public: 8128edf954 2013-12-15 kinaba: vector<int> similarRooms(vector<string> maze) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: map<int,int> e2o; 8128edf954 2013-12-15 kinaba: Graph org = parse_graph(maze); // original graph 8128edf954 2013-12-15 kinaba: Graph exg = construct_extended_graph(org, &e2o); // extended graph 8128edf954 2013-12-15 kinaba: Groups groups = grouping(exg); // grouping 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: // similar[ov] = set of nodes indistinguishable from ov (in original graph) 8128edf954 2013-12-15 kinaba: vector<set<int>> similar(maze.size()); 8128edf954 2013-12-15 kinaba: for(auto& e_grp: groups) { 8128edf954 2013-12-15 kinaba: set<int> o_grp; 8128edf954 2013-12-15 kinaba: for(int ev: e_grp) 8128edf954 2013-12-15 kinaba: o_grp.insert(e2o[ev]); 8128edf954 2013-12-15 kinaba: for(int ov: o_grp) 8128edf954 2013-12-15 kinaba: similar[ov].insert(o_grp.begin(), o_grp.end()); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: // similar[ov]-1 is the answer. 8128edf954 2013-12-15 kinaba: vector<int> answer(maze.size()); 8128edf954 2013-12-15 kinaba: transform(similar.begin(), similar.end(), answer.begin(), 8128edf954 2013-12-15 kinaba: [](const set<int>& g){return g.size()-1;}); 8128edf954 2013-12-15 kinaba: return answer; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: typedef vector<vector<int>> Graph; 8128edf954 2013-12-15 kinaba: Graph parse_graph(const vector<string>& maze) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: Graph g; 8128edf954 2013-12-15 kinaba: for(auto& m: maze) { 8128edf954 2013-12-15 kinaba: stringstream ss(m); 8128edf954 2013-12-15 kinaba: g.emplace_back(istream_iterator<int>(ss), istream_iterator<int>()); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: return g; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: Graph construct_extended_graph(const Graph& org, map<int,int>* e2o) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: map<pair<int,int>, int> o2e; 8128edf954 2013-12-15 kinaba: for(int v=0,id=0; v<org.size(); ++v) { 8128edf954 2013-12-15 kinaba: // special handling for outdeg = 0 node 8128edf954 2013-12-15 kinaba: if(org[v].size() == 0) { 8128edf954 2013-12-15 kinaba: (*e2o)[id] = v; 8128edf954 2013-12-15 kinaba: o2e[make_pair(v,0)] = id++; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: for(int vi=0; vi<org[v].size(); ++vi) { 8128edf954 2013-12-15 kinaba: (*e2o)[id] = v; 8128edf954 2013-12-15 kinaba: o2e[make_pair(v,vi)] = id++; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: Graph exg(o2e.size()); 8128edf954 2013-12-15 kinaba: map<pair<int,int>, int> nodeid; 8128edf954 2013-12-15 kinaba: for(int v=0; v<org.size(); ++v) 8128edf954 2013-12-15 kinaba: for(int vi=0; vi<org[v].size(); ++vi) { 8128edf954 2013-12-15 kinaba: // (v,vi) : came to the room v from the vi-th road. 8128edf954 2013-12-15 kinaba: for(int k=0; k<org[v].size(); ++k) { 8128edf954 2013-12-15 kinaba: // Go k-th road clockwise from i-th. Reaches (u,ui). 8128edf954 2013-12-15 kinaba: int u = org[v][(vi+k) % org[v].size()]; 8128edf954 2013-12-15 kinaba: int ui = find(org[u].begin(), org[u].end(), v) - org[u].begin(); 8128edf954 2013-12-15 kinaba: // (v,vi)--k-->(u,ui) 8128edf954 2013-12-15 kinaba: exg[o2e[make_pair(v,vi)]].push_back(o2e[make_pair(u,ui)]); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: return exg; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: typedef set<set<int>> Groups; 8128edf954 2013-12-15 kinaba: Groups grouping(const Graph& G) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: // "reverse_edge[u][e] has v" := v--e-->u 8128edf954 2013-12-15 kinaba: const int MaxEdgeNum = G.size(); 8128edf954 2013-12-15 kinaba: vector<vector<vector<int>>> reverse_edge(G.size(), vector<vector<int>>(MaxEdgeNum)); 8128edf954 2013-12-15 kinaba: for(int v=0; v<G.size(); ++v) 8128edf954 2013-12-15 kinaba: for(int e=0; e<G[v].size(); ++e) 8128edf954 2013-12-15 kinaba: reverse_edge[G[v][e]][e].push_back(v); 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: vector<int> group_id(G.size()); 8128edf954 2013-12-15 kinaba: map<int, set<int>> groups; 8128edf954 2013-12-15 kinaba: int fresh_group_id = 0; 8128edf954 2013-12-15 kinaba: for(int v=0; v<G.size(); ++v) { 8128edf954 2013-12-15 kinaba: groups[G[v].size()].insert(v); 8128edf954 2013-12-15 kinaba: group_id[v] = G[v].size(); 8128edf954 2013-12-15 kinaba: fresh_group_id = max(fresh_group_id, group_id[v]+1); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: queue<set<int>> partitioner; 8128edf954 2013-12-15 kinaba: for(auto& kv: groups) 8128edf954 2013-12-15 kinaba: partitioner.push(kv.second); 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: while(!partitioner.empty()) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: set<int> P = partitioner.front(); 8128edf954 2013-12-15 kinaba: partitioner.pop(); 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: for(int e=0; e<MaxEdgeNum; ++e) 8128edf954 2013-12-15 kinaba: { 8128edf954 2013-12-15 kinaba: map<int, set<int>> g2u; 8128edf954 2013-12-15 kinaba: for(int v: P) 8128edf954 2013-12-15 kinaba: for(int u: reverse_edge[v][e]) 8128edf954 2013-12-15 kinaba: g2u[group_id[u]].insert(u); 8128edf954 2013-12-15 kinaba: for(auto& kv: g2u) { 8128edf954 2013-12-15 kinaba: int gid = kv.first; 8128edf954 2013-12-15 kinaba: set<int>& enterP = kv.second; 8128edf954 2013-12-15 kinaba: if(groups[gid].size() != enterP.size()) { 8128edf954 2013-12-15 kinaba: for(int u: enterP) { 8128edf954 2013-12-15 kinaba: group_id[u] = fresh_group_id; 8128edf954 2013-12-15 kinaba: groups[gid].erase(u); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: groups[fresh_group_id++] = enterP; 8128edf954 2013-12-15 kinaba: partitioner.push(enterP.size() < groups[gid].size() ? enterP : groups[gid]); 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: Groups result; 8128edf954 2013-12-15 kinaba: for(auto& kv: groups) 8128edf954 2013-12-15 kinaba: result.insert(kv.second); 8128edf954 2013-12-15 kinaba: return result; 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: }; 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: // BEGIN CUT HERE 8128edf954 2013-12-15 kinaba: #include <ctime> 8128edf954 2013-12-15 kinaba: double start_time; string timer() 8128edf954 2013-12-15 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 8128edf954 2013-12-15 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 8128edf954 2013-12-15 kinaba: { os << "{ "; 8128edf954 2013-12-15 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 8128edf954 2013-12-15 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 8128edf954 2013-12-15 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { 8128edf954 2013-12-15 kinaba: bool ok = (Expected == Received); 8128edf954 2013-12-15 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 8128edf954 2013-12-15 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 8128edf954 2013-12-15 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 8128edf954 2013-12-15 kinaba: #define END verify_case(_, TwistyPassages().similarRooms(maze));} 8128edf954 2013-12-15 kinaba: int main(){ 8128edf954 2013-12-15 kinaba: 8128edf954 2013-12-15 kinaba: CASE(0) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2 3", "0", "0", "0"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {0, 2, 2, 2 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(1) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2 3", "0", "0", "0 4", "3"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {0, 0, 0, 0, 0 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(2) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2 3", "0", "0", "0 4", "3", 8128edf954 2013-12-15 kinaba: "6 7 8", "5", "5", "5 9", "8"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(3) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2 3 4", "0", "0 5", "0", "6 0", "2", "4", 8128edf954 2013-12-15 kinaba: "8 10 9 11", "7", "7 12", "7", "13 7", "9", "11"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(4) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2", "2 0", "0 1", "4 6", "5 3", "6 4", "3 5"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {6, 6, 6, 6, 6, 6, 6 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(5) 8128edf954 2013-12-15 kinaba: string maze_[] = {"1 2 3", "4 5 0", "6 7 0", "8 9 0", "10 11 1", "12 13 1", 8128edf954 2013-12-15 kinaba: "14 15 2", "16 17 2", "18 19 3", "20 21 3", "22 23 4", 8128edf954 2013-12-15 kinaba: "24 25 4", "26 27 5", "28 29 5", "30 31 6", "32 33 6", 8128edf954 2013-12-15 kinaba: "34 35 7", "36 37 7", "38 39 8", "40 41 8", "42 43 9", 8128edf954 2013-12-15 kinaba: "44 45 9", "10", "10", "11", "11", "12", "12", "13", "13", 8128edf954 2013-12-15 kinaba: "14", "14", "15", "15", "16", "16", "17", "17", "18", "18", 8128edf954 2013-12-15 kinaba: "19", "19", "20", "20", "21", "21"}; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: CASE(6) 8128edf954 2013-12-15 kinaba: string maze_[] = {"38 7 9 8 43 48 30 41 5 22 26 35 33 4", "14 39 25 35 30 45 18 12 10 8 21 46 22 37 20", "15 37 26 44 19 17 39 16 7 18 45 36 20 42 24", "21 43 26 8 28 10 4 48 25 46 49 31 37 27 15", "8 31 30 3 0 36 41 5 34 25 44 32 9 14 22", "46 33 38 4 47 34 17 6 45 10 41 48 31 43 0", "5 40 17 19 22 43 18 47 31 9 7 15 29 28 23", "19 38 21 11 34 31 9 0 48 30 44 2 26 16 6", "48 12 3 49 0 41 1 28 35 40 36 4 29 33 43", "18 36 6 47 26 37 27 22 0 46 23 41 4 24 7", "42 13 35 28 31 12 11 3 1 20 16 45 19 40 5", "14 15 45 46 13 7 27 39 25 38 44 17 16 10 43", "48 8 15 42 47 10 29 45 39 1 19 25 44 32 26", "47 24 11 36 41 42 16 38 37 20 32 31 45 29 10", "31 48 49 25 11 38 18 23 43 4 22 41 24 1 27", "32 34 23 11 6 43 2 22 48 45 17 41 12 16 3", "7 46 18 28 20 19 43 31 27 2 15 13 39 10 11", "19 26 28 2 30 23 15 5 24 47 25 18 6 42 11", "26 6 24 46 17 42 45 14 16 9 22 27 1 33 2", "30 6 17 37 39 33 49 2 21 46 16 27 7 10 12", "13 32 41 1 39 16 42 27 2 33 40 24 45 48 10", "36 37 41 1 30 7 23 35 40 44 26 47 39 3 19", "14 6 23 40 0 43 9 29 1 18 31 15 28 34 4", "30 14 6 28 34 22 48 9 40 21 42 17 15 37 32", "48 40 44 26 9 20 13 43 17 2 18 29 14 42 46", "32 12 43 1 17 39 29 14 3 36 11 40 4 49 33", "0 7 39 3 12 49 38 36 21 29 18 17 9 2 24", "29 28 38 16 18 46 9 3 35 36 40 20 14 11 19", "33 39 35 38 3 6 22 10 23 17 27 46 16 8 42", "13 26 25 37 33 44 12 48 6 41 46 24 8 22 27", "34 41 38 21 0 19 23 4 7 49 1 44 17 40 35", "3 14 32 4 5 37 7 6 13 10 22 16 44 47 49", "15 4 13 31 38 23 42 20 12 46 35 25 43 34 37", "39 44 19 0 18 28 20 37 29 48 8 45 25 5 34", "36 44 47 7 15 4 33 30 42 32 22 40 5 23 41", "40 27 42 8 45 32 10 0 28 1 49 46 30 47 21", "4 2 21 47 8 38 27 45 39 13 49 26 9 25 34", "42 21 31 29 13 47 32 3 9 33 2 23 45 1 19", "0 43 7 28 44 13 27 32 49 14 36 11 5 30 26", "16 36 21 20 12 48 26 41 2 11 28 33 1 19 25", "8 22 10 6 35 20 25 23 41 27 30 24 44 34 21", "13 29 39 15 0 30 40 20 4 5 34 14 8 9 21", "28 10 32 17 34 37 13 2 18 20 12 24 35 49 23", "5 47 25 24 11 8 14 38 16 6 32 15 22 3 0", "40 38 30 21 31 46 34 29 11 33 4 12 24 2 7", "35 49 36 10 12 11 37 18 33 2 20 1 13 15 5", "3 28 35 1 19 9 18 27 32 44 24 11 29 16 5", "9 43 6 31 12 13 35 21 36 5 49 34 48 17 37", "24 33 5 8 15 12 47 29 0 7 23 20 14 39 3", "19 3 14 8 38 47 30 36 35 25 31 26 42 45"}; 8128edf954 2013-12-15 kinaba: ; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = {0}; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: /* 8128edf954 2013-12-15 kinaba: CASE(7) 8128edf954 2013-12-15 kinaba: string maze_[] = ; 8128edf954 2013-12-15 kinaba: vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 8128edf954 2013-12-15 kinaba: int __[] = ; 8128edf954 2013-12-15 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 8128edf954 2013-12-15 kinaba: END 8128edf954 2013-12-15 kinaba: */ 8128edf954 2013-12-15 kinaba: } 8128edf954 2013-12-15 kinaba: // END CUT HERE