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

Added SRM/682-U/1A.cpp version [20ca2592f0879134]

            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  +#include <cstring>
           19  +using namespace std;
           20  +typedef long long LL;
           21  +typedef complex<double> CMP;
           22  +
           23  +LL nei[2000][32];
           24  +
           25  +class SmilesTheFriendshipUnicorn { public:
           26  + string hasFriendshipChain(int N, vector <int> A, vector <int> B)
           27  + {
           28  +  return solve(N, A, B) ? "Yay!" : ":(";
           29  + }
           30  +
           31  + bool solve(int N, const vector<int>& A, const vector<int>& B)
           32  + {
           33  +  vector<vector<int>> G(N);
           34  +  for(int i=0; i<A.size(); ++i) {
           35  +   G[A[i]].push_back(B[i]);
           36  +   G[B[i]].push_back(A[i]);
           37  +  }
           38  +
           39  +  memset(&nei, 0, sizeof(nei));
           40  +
           41  +  for(int i=0; i<A.size(); ++i) {
           42  +   for(int u: G[A[i]])
           43  +    nei[i][u>>6] |= 1LL<<(u&0x3f);
           44  +   for(int u: G[B[i]])
           45  +    nei[i][u>>6] |= 1LL<<(u&0x3f);
           46  +   nei[i][A[i]>>6] &= ~(1LL<<(A[i]&0x3f));
           47  +   nei[i][B[i]>>6] &= ~(1LL<<(B[i]&0x3f));
           48  +  }
           49  +
           50  +  for(int i=0; i<A.size(); ++i)
           51  +  for(int k=i+1; k<A.size(); ++k)
           52  +  if(A[i]!=A[k] && A[i]!=B[k] && B[i]!=A[k] && B[i]!=B[k])
           53  +   for(int v=0; v<32; ++v)
           54  +    if(nei[i][v] & nei[k][v])
           55  +     return true;
           56  +  return false;
           57  + }
           58  +};
           59  +
           60  +// BEGIN CUT HERE
           61  +#include <ctime>
           62  +double start_time; string timer()
           63  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           64  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           65  + { os << "{ ";
           66  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           67  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           68  +void verify_case(const string& Expected, const string& Received) {
           69  + bool ok = (Expected == Received);
           70  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           71  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           72  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           73  +#define END  verify_case(_, SmilesTheFriendshipUnicorn().hasFriendshipChain(N, A, B));}
           74  +int main(){
           75  +
           76  +CASE(0)
           77  + int N = 5;
           78  + int A_[] = {0, 1, 2, 3};
           79  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           80  + int B_[] = {1, 2, 3, 4};
           81  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           82  + string _ = "Yay!";
           83  +END
           84  +CASE(1)
           85  + int N = 5;
           86  + int A_[] = {0, 1, 2, 3, 1};
           87  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           88  + int B_[] = {1, 2, 3, 0, 4};
           89  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           90  + string _ = "Yay!";
           91  +END
           92  +CASE(2)
           93  + int N = 6;
           94  + int A_[] = {0, 0, 0, 0, 0};
           95  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           96  + int B_[] = {1, 2, 3, 4, 5};
           97  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           98  + string _ = ":(";
           99  +END
          100  +CASE(3)
          101  + int N = 8;
          102  + int A_[] = {1, 3, 4, 3, 4, 3, 0, 2};
          103  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          104  + int B_[] = {7, 7, 7, 4, 6, 5, 4, 7};
          105  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          106  + string _ = "Yay!";
          107  +END
          108  +CASE(4)
          109  + int N = 7;
          110  + int A_[] = {0, 1, 1, 5, 4, 5};
          111  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          112  + int B_[] = {5, 2, 3, 6, 1, 1};
          113  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          114  + string _ = ":(";
          115  +END
          116  +CASE(5)
          117  + int N = 42;
          118  + int A_[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41}
          119  +;
          120  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          121  + int B_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 0};
          122  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          123  + string _ = "Yay!";
          124  +END
          125  +/*
          126  +CASE(6)
          127  + int N = ;
          128  + int A_[] = ;
          129  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          130  + int B_[] = ;
          131  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          132  + string _ = ;
          133  +END
          134  +CASE(7)
          135  + int N = ;
          136  + int A_[] = ;
          137  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          138  + int B_[] = ;
          139  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          140  + string _ = ;
          141  +END
          142  +*/
          143  +}
          144  +// END CUT HERE

Added SRM/682-U/1B.cpp version [7dc731da039a3f44]

            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  +set<int> detect_cycle(int N, const vector<vector<int>>& G)
           23  +{
           24  + vector<int> stk;
           25  + set<int> cycle;
           26  + function<void(int,int)> rec = [&](int pre, int v) {
           27  +  stk.push_back(v);
           28  +  for(int u: G[v]) if(u != pre) {
           29  +   auto it = find(stk.begin(), stk.end(), u);
           30  +   if(it == stk.end()) {
           31  +    rec(v, u);
           32  +   } else {
           33  +    cycle = set<int>(it, stk.end());
           34  +   }
           35  +  }
           36  +  stk.pop_back();
           37  + };
           38  + rec(-1, 0);
           39  + return cycle;
           40  +}
           41  +
           42  +vector<vector<int>> flatten(const vector<set<int>>& GS)
           43  +{
           44  + vector<vector<int>> G;
           45  + for(const auto& s: GS)
           46  +  G.emplace_back(s.begin(), s.end());
           47  + return G;
           48  +}
           49  +
           50  +class SuccessfulMerger { public:
           51  + int minimumMergers(vector <int> road)
           52  + {
           53  +  const int N = road.size();
           54  +  vector<set<int>> Gs(N);
           55  +  for(int i=0; i<N; ++i) {
           56  +   Gs[i].insert(road[i]);
           57  +   Gs[road[i]].insert(i);
           58  +  }
           59  +  vector<vector<int>> G = flatten(Gs);
           60  +
           61  +  set<int> cy = detect_cycle(N, G);
           62  +  if(cy.empty())
           63  +   return solve(N, G);
           64  +
           65  +  int best = N-1;
           66  +  set<int> cyl = cy;
           67  +  for(int survive: cyl) {
           68  +   cy.erase(survive);
           69  +
           70  +   map<int,int> remap;
           71  +   int XN = N - cy.size() + 1;
           72  +   for(int v=0; v<N; ++v) {
           73  +    if(cy.count(v)) {
           74  +     remap[v] = XN - 1;
           75  +    } else {
           76  +     int idx = 0;
           77  +     for(int u=0; u<v; ++u)
           78  +      if(!cy.count(u))
           79  +       ++idx;
           80  +     remap[v] = idx;
           81  +    }
           82  +   }
           83  +   vector<set<int>> XGs(XN);
           84  +   for(int i=0; i<N; ++i) {
           85  +    int a = remap[i];
           86  +    int b = remap[road[i]];
           87  +    if(a != b) {
           88  +     XGs[a].insert(b);
           89  +     XGs[b].insert(a);
           90  +    }
           91  +   }
           92  +   vector<vector<int>> XG = flatten(XGs);
           93  +   best = min<int>(best, solve(XN, XG) + cy.size() - 1);
           94  +
           95  +   cy.insert(survive);
           96  +  }
           97  +  return best;
           98  + }
           99  +
          100  + int solve(int N, const vector<vector<int>>& G) {
          101  +  if(N <= 2)
          102  +   return 0;
          103  +
          104  +  int best = N-1;
          105  +  for(int root=0; root<N; ++root)
          106  +   best = min(best, solve(N, root, G));
          107  +  return best;
          108  + }
          109  +
          110  + int solve(int N, int root, const vector<vector<int>>& G)
          111  + {
          112  +  function<int(int,int)> non_leaf_cnt = [&](int pre, int v) {
          113  +   if(G[v].size() == 1)
          114  +    return 0;
          115  +   int sum = 1;
          116  +   for(int u: G[v]) if(u != pre)
          117  +    sum += non_leaf_cnt(v, u);
          118  +   return sum;
          119  +  };
          120  +
          121  +  int total = 0;
          122  +  for(int ch: G[root])
          123  +   total += non_leaf_cnt(root, ch);
          124  +  return total;
          125  + }
          126  +};
          127  +
          128  +// BEGIN CUT HERE
          129  +#include <ctime>
          130  +double start_time; string timer()
          131  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          132  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          133  + { os << "{ ";
          134  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          135  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          136  +void verify_case(const int& Expected, const int& Received) {
          137  + bool ok = (Expected == Received);
          138  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          139  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          140  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          141  +#define END  verify_case(_, SuccessfulMerger().minimumMergers(road));}
          142  +int main(){
          143  +
          144  +CASE(0)
          145  + int road_[] = {2, 2, 1, 1, 1};
          146  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          147  + int _ = 1;
          148  +END
          149  +CASE(1)
          150  + int road_[] = {3, 4, 5, 4, 5, 3};
          151  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          152  + int _ = 2;
          153  +END
          154  +CASE(2)
          155  + int road_[] = {1, 0, 1, 0, 0, 0, 1, 0, 1, 1};
          156  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          157  + int _ = 1;
          158  +END
          159  +CASE(3)
          160  + int road_[] = {1, 2, 3, 0};
          161  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          162  + int _ = 2;
          163  +END
          164  +CASE(4)
          165  + int road_[] = {31, 19, 0, 15, 30, 32, 15, 24, 0, 20, 40, 1, 22, 21, 39, 28, 0, 23, 15, 5, 19, 22, 6, 32, 8, 38, 35, 30, 4, 28, 32, 18, 18, 9, 22, 41, 20, 18, 6, 25, 41, 34, 4};
          166  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          167  + int _ = 25;
          168  +END
          169  +CASE(5)
          170  + int road_[] = {1, 0};
          171  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          172  + int _ = 0;
          173  +END
          174  +/*
          175  +CASE(6)
          176  + int road_[] = ;
          177  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          178  + int _ = ;
          179  +END
          180  +CASE(7)
          181  + int road_[] = ;
          182  +   vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
          183  + int _ = ;
          184  +END
          185  +*/
          186  +}
          187  +// END CUT HERE