Overview
| SHA1 Hash: | 8128edf954a98f6553c3d68beead9019109aba93 |
|---|---|
| Date: | 2013-12-15 16:01:46 |
| User: | kinaba |
| Comment: | 378 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/378-U/1C.cpp version [bb3522cbac3e711c]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TwistyPassages { public: > 23 vector<int> similarRooms(vector<string> maze) > 24 { > 25 map<int,int> e2o; > 26 Graph org = parse_graph(maze); // original graph > 27 Graph exg = construct_extended_graph(org, &e2o); // extended gra > 28 Groups groups = grouping(exg); // grouping > 29 > 30 // similar[ov] = set of nodes indistinguishable from ov (in orig > 31 vector<set<int>> similar(maze.size()); > 32 for(auto& e_grp: groups) { > 33 set<int> o_grp; > 34 for(int ev: e_grp) > 35 o_grp.insert(e2o[ev]); > 36 for(int ov: o_grp) > 37 similar[ov].insert(o_grp.begin(), o_grp.end()); > 38 } > 39 > 40 // similar[ov]-1 is the answer. > 41 vector<int> answer(maze.size()); > 42 transform(similar.begin(), similar.end(), answer.begin(), > 43 [](const set<int>& g){return g.size()-1;}); > 44 return answer; > 45 } > 46 > 47 typedef vector<vector<int>> Graph; > 48 Graph parse_graph(const vector<string>& maze) > 49 { > 50 Graph g; > 51 for(auto& m: maze) { > 52 stringstream ss(m); > 53 g.emplace_back(istream_iterator<int>(ss), istream_iterat > 54 } > 55 return g; > 56 } > 57 > 58 Graph construct_extended_graph(const Graph& org, map<int,int>* e2o) > 59 { > 60 map<pair<int,int>, int> o2e; > 61 for(int v=0,id=0; v<org.size(); ++v) { > 62 // special handling for outdeg = 0 node > 63 if(org[v].size() == 0) { > 64 (*e2o)[id] = v; > 65 o2e[make_pair(v,0)] = id++; > 66 } > 67 for(int vi=0; vi<org[v].size(); ++vi) { > 68 (*e2o)[id] = v; > 69 o2e[make_pair(v,vi)] = id++; > 70 } > 71 } > 72 > 73 Graph exg(o2e.size()); > 74 map<pair<int,int>, int> nodeid; > 75 for(int v=0; v<org.size(); ++v) > 76 for(int vi=0; vi<org[v].size(); ++vi) { > 77 // (v,vi) : came to the room v from the vi-th road. > 78 for(int k=0; k<org[v].size(); ++k) { > 79 // Go k-th road clockwise from i-th. Reaches (u, > 80 int u = org[v][(vi+k) % org[v].size()]; > 81 int ui = find(org[u].begin(), org[u].end(), v) - > 82 // (v,vi)--k-->(u,ui) > 83 exg[o2e[make_pair(v,vi)]].push_back(o2e[make_pai > 84 } > 85 } > 86 return exg; > 87 } > 88 > 89 typedef set<set<int>> Groups; > 90 Groups grouping(const Graph& G) > 91 { > 92 // "reverse_edge[u][e] has v" := v--e-->u > 93 const int MaxEdgeNum = G.size(); > 94 vector<vector<vector<int>>> reverse_edge(G.size(), vector<vector > 95 for(int v=0; v<G.size(); ++v) > 96 for(int e=0; e<G[v].size(); ++e) > 97 reverse_edge[G[v][e]][e].push_back(v); > 98 > 99 vector<int> group_id(G.size()); > 100 map<int, set<int>> groups; > 101 int fresh_group_id = 0; > 102 for(int v=0; v<G.size(); ++v) { > 103 groups[G[v].size()].insert(v); > 104 group_id[v] = G[v].size(); > 105 fresh_group_id = max(fresh_group_id, group_id[v]+1); > 106 } > 107 > 108 queue<set<int>> partitioner; > 109 for(auto& kv: groups) > 110 partitioner.push(kv.second); > 111 > 112 while(!partitioner.empty()) > 113 { > 114 set<int> P = partitioner.front(); > 115 partitioner.pop(); > 116 > 117 for(int e=0; e<MaxEdgeNum; ++e) > 118 { > 119 map<int, set<int>> g2u; > 120 for(int v: P) > 121 for(int u: reverse_edge[v][e]) > 122 g2u[group_id[u]].insert(u); > 123 for(auto& kv: g2u) { > 124 int gid = kv.first; > 125 set<int>& enterP = kv.second; > 126 if(groups[gid].size() != enterP.size()) > 127 for(int u: enterP) { > 128 group_id[u] = fresh_grou > 129 groups[gid].erase(u); > 130 } > 131 groups[fresh_group_id++] = enter > 132 partitioner.push(enterP.size() < > 133 } > 134 } > 135 } > 136 } > 137 > 138 Groups result; > 139 for(auto& kv: groups) > 140 result.insert(kv.second); > 141 return result; > 142 } > 143 }; > 144 > 145 // BEGIN CUT HERE > 146 #include <ctime> > 147 double start_time; string timer() > 148 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 149 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 150 { os << "{ "; > 151 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 152 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 153 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 154 bool ok = (Expected == Received); > 155 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 156 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 157 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 158 #define END verify_case(_, TwistyPassages().similarRooms(maze));} > 159 int main(){ > 160 > 161 CASE(0) > 162 string maze_[] = {"1 2 3", "0", "0", "0"}; > 163 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 164 int __[] = {0, 2, 2, 2 }; > 165 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 166 END > 167 CASE(1) > 168 string maze_[] = {"1 2 3", "0", "0", "0 4", "3"}; > 169 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 170 int __[] = {0, 0, 0, 0, 0 }; > 171 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 172 END > 173 CASE(2) > 174 string maze_[] = {"1 2 3", "0", "0", "0 4", "3", > 175 "6 7 8", "5", "5", "5 9", "8"}; > 176 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 177 int __[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; > 178 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 179 END > 180 CASE(3) > 181 string maze_[] = {"1 2 3 4", "0", "0 5", "0", "6 0", "2", "4", > 182 "8 10 9 11", "7", "7 12", "7", "13 7", "9", "11"}; > 183 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 184 int __[] = {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }; > 185 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 186 END > 187 CASE(4) > 188 string maze_[] = {"1 2", "2 0", "0 1", "4 6", "5 3", "6 4", "3 5"}; > 189 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 190 int __[] = {6, 6, 6, 6, 6, 6, 6 }; > 191 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 192 END > 193 CASE(5) > 194 string maze_[] = {"1 2 3", "4 5 0", "6 7 0", "8 9 0", "10 11 1", "12 13 > 195 "14 15 2", "16 17 2", "18 19 3", "20 21 3", "22 23 4", > 196 "24 25 4", "26 27 5", "28 29 5", "30 31 6", "32 33 6", > 197 "34 35 7", "36 37 7", "38 39 8", "40 41 8", "42 43 9", > 198 "44 45 9", "10", "10", "11", "11", "12", "12", "13", "13", > 199 "14", "14", "15", "15", "16", "16", "17", "17", "18", "18", > 200 "19", "19", "20", "20", "21", "21"}; > 201 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 202 int __[] = {0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, > 203 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 204 END > 205 CASE(6) > 206 string maze_[] = {"38 7 9 8 43 48 30 41 5 22 26 35 33 4", "14 39 25 35 3 > 207 ; > 208 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 209 int __[] = {0}; > 210 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 211 END > 212 /* > 213 CASE(7) > 214 string maze_[] = ; > 215 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 216 int __[] = ; > 217 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 218 END > 219 */ > 220 } > 221 // END CUT HERE