Overview
| SHA1 Hash: | 062d1ffb7ce27aca460995dd96e5f8cfc046841c |
|---|---|
| Date: | 2016-03-28 12:08:27 |
| User: | kinaba |
| Comment: | 682. |
| 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/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) > 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 > 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() > 71 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 72 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 73 #define END verify_case(_, SmilesTheFriendshipUnicorn().hasFriendshipChain( > 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 > 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, 1 > 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) > 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 > 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() > 139 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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