• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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 graph
           28  +  Groups groups = grouping(exg); // grouping
           29  +
           30  +  // similar[ov] = set of nodes indistinguishable from ov (in original graph)
           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_iterator<int>());
           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,ui).
           80  +    int u = org[v][(vi+k) % org[v].size()];
           81  +    int ui = find(org[u].begin(), org[u].end(), v) - org[u].begin();
           82  +    // (v,vi)--k-->(u,ui)
           83  +    exg[o2e[make_pair(v,vi)]].push_back(o2e[make_pair(u,ui)]);
           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<int>>(MaxEdgeNum));
           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_group_id;
          129  +       groups[gid].erase(u);
          130  +      }
          131  +      groups[fresh_group_id++] = enterP;
          132  +      partitioner.push(enterP.size() < groups[gid].size() ? enterP : groups[gid]);
          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) << " msec)"; return os.str(); }
          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 os; }
          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() << endl;
          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 1",
          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, 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 };
          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 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"};
          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