Overview
| SHA1 Hash: | 06a6ad17f5f7f8a888d27cfc501f53c87618c212 |
|---|---|
| Date: | 2020-09-10 16:54:39 |
| User: | kinaba |
| Comment: | 790 |
| 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/790-U/1A.cpp version [5858693d18cedfa3]
> 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 struct UnionFind > 23 { > 24 vector<int> uf, sz; > 25 int nc; > 26 > 27 UnionFind(int N) : uf(N), sz(N, 1), nc(N) > 28 { > 29 for (int i = 0; i<N; ++i) uf[i] = i; > 30 } > 31 int size() > 32 { > 33 return nc; > 34 } > 35 int size(int a) > 36 { > 37 return sz[Find(a)]; > 38 } > 39 int Find(int a) > 40 { > 41 return uf[a] == a ? a : uf[a] = Find(uf[a]); > 42 } > 43 // Semi-compression w.o. recursion. > 44 //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; } > 45 bool Union(int a, int b) > 46 { > 47 a = Find(a); > 48 b = Find(b); > 49 if (a != b) > 50 { > 51 if (sz[a] >= sz[b]) swap(a, b); > 52 uf[a] = b; > 53 sz[b] += sz[a]; > 54 --nc; > 55 } > 56 return (a != b); > 57 } > 58 }; > 59 > 60 static const unsigned MODVAL = 1000000007; > 61 struct mint > 62 { > 63 unsigned val; > 64 mint() :val(0) {} > 65 mint(int x) :val(x%MODVAL) {} > 66 mint(unsigned x) :val(x%MODVAL) {} > 67 mint(LL x) :val(x%MODVAL) {} > 68 }; > 69 mint& operator+=(mint& x, mint y) { return x = x.val + y.val; } > 70 mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; } > 71 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 72 mint operator+(mint x, mint y) { return x += y; } > 73 mint operator-(mint x, mint y) { return x -= y; } > 74 mint operator*(mint x, mint y) { return x *= y; } > 75 > 76 mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= > 77 > 78 class TheSocialNetwork { public: > 79 int minimumCut(int n, int m, vector <int> u, vector <int> v, vector <int > 80 { > 81 vector<tuple<int, int, int>> e; > 82 for (int i = 0; i < m; ++i) > 83 e.emplace_back(l[i], u[i]-1, v[i]-1); > 84 sort(e.begin(), e.end()); > 85 > 86 vector<bool> use(m, false); > 87 for (int k = e.size() - 1; k >= 0; --k) { > 88 use[k] = true; > 89 if (is_connected(n, m, use, e)) > 90 use[k] = false; > 91 } > 92 > 93 mint ans = 0; > 94 for (int i = 0; i < m; ++i) if (!use[i]) > 95 ans += POW(2, get<0>(e[i])); > 96 return ans.val; > 97 } > 98 > 99 bool is_connected(int n, int m, const vector<bool>& use, const vector<tu > 100 UnionFind uf(n); > 101 for (int i = 0; i < m; ++i) if (use[i]) > 102 uf.Union(get<1>(e[i]), get<2>(e[i])); > 103 return uf.size() == 1; > 104 > 105 } > 106 }; > 107 > 108 // BEGIN CUT HERE > 109 #include <ctime> > 110 double start_time; string timer() > 111 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 112 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 113 { os << "{ "; > 114 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 115 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 116 void verify_case(const int& Expected, const int& Received) { > 117 bool ok = (Expected == Received); > 118 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 119 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 120 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 121 #define END verify_case(_, TheSocialNetwork().minimumCut(n, m, u, v, l));} > 122 int main(){ > 123 > 124 CASE(0) > 125 int n = 6; > 126 int m = 6; > 127 int u_[] = {1, 2, 3, 4, 5, 6} ; > 128 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 129 int v_[] = {2, 3, 4, 5, 6, 1}; > 130 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 131 int l_[] = {1, 7, 3, 4, 6, 12}; > 132 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 133 int _ = 10; > 134 END > 135 CASE(1) > 136 int n = 5; > 137 int m = 7; > 138 int u_[] = {1, 1, 1, 2, 2, 3, 3}; > 139 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 140 int v_[] = {5, 3, 2, 5, 3, 5, 4}; > 141 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 142 int l_[] = {1, 8, 2, 3, 4, 6, 9}; > 143 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 144 int _ = 28; > 145 END > 146 CASE(2) > 147 int n = 7; > 148 int m = 6; > 149 int u_[] = {1, 1, 2, 2, 3, 3}; > 150 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 151 int v_[] = {2, 3, 4, 5, 6, 7}; > 152 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 153 int l_[] = {7, 11, 6, 9, 20, 15}; > 154 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 155 int _ = 64; > 156 END > 157 CASE(3) > 158 int n = 8; > 159 int m = 11; > 160 int u_[] = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7}; > 161 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 162 int v_[] = {2, 8, 3, 5, 4, 6, 7, 5, 6, 8, 8}; > 163 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 164 int l_[] = {2, 3, 1, 6, 11, 8, 9, 10, 7, 4, 5}; > 165 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 166 int _ = 12; > 167 END > 168 CASE(4) > 169 int n = 13; > 170 int m = 56; > 171 int u_[] = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, > 172 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 173 int v_[] = {3, 4, 5, 7, 9, 12, 13, 3, 5, 8, 9, 10, 12, 13, 5, 6, 8, 9, 1 > 174 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 175 int l_[] = {82, 240, 395, 1041, 1165, 1274, 1540, 1650, 1904, 2306, 2508 > 176 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 177 int _ = 504663883; > 178 END > 179 /* > 180 CASE(5) > 181 int n = ; > 182 int m = ; > 183 int u_[] = ; > 184 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 185 int v_[] = ; > 186 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 187 int l_[] = ; > 188 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 189 int _ = ; > 190 END > 191 CASE(6) > 192 int n = ; > 193 int m = ; > 194 int u_[] = ; > 195 vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); > 196 int v_[] = ; > 197 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 198 int l_[] = ; > 199 vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); > 200 int _ = ; > 201 END > 202 */ > 203 } > 204 // END CUT HERE
Added SRM/790-U/1B.cpp version [f1a66c485fe2d09f]
> 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 ProposalOptimization { public: > 23 double bestPath(int R, int C, int K, vector <int> roses, vector <int> tu > 24 { > 25 int S = (R - 1) + (C - 1); > 26 > 27 vector<vector<tuple<LL, LL, LL>>> cand1(R*C), cand2(R*C); > 28 dfs1(R, C, K, roses, tulips, costs, 0, 0, S/2, 0LL, 0LL, 0LL, ca > 29 dfs2(R, C, K, roses, tulips, costs, R-1, C-1, S-S/2, 0LL, 0LL, 0 > 30 > 31 double best = -1; > 32 for (int i = 0; i < cand1.size(); ++i) > 33 if (!cand1[i].empty() && !cand2[i].empty()) > 34 best = max(best, calc_best(cand1[i], cand2[i], K > 35 return best; > 36 } > 37 > 38 double calc_best( > 39 vector<tuple<LL, LL, LL>> c1, > 40 vector<tuple<LL, LL, LL>> c2, > 41 int K > 42 ) { > 43 sort(c1.begin(), c1.end(), [&](const tuple<LL, LL, LL>& a, const > 44 return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) > 45 }); > 46 sort(c2.begin(), c2.end(), [&](const tuple<LL, LL, LL>& a, const > 47 return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) > 48 }); > 49 double best = -1; > 50 for (auto&& e1 : c1) { > 51 LL r1, t1, co1; tie(r1, t1, co1) = e1; > 52 double rat1 = double(r1) / t1; > 53 for (auto&& e2 : c2) { > 54 LL r2, t2, co2; tie(r2, t2, co2) = e2; > 55 double rat2 = double(r2) / t2; > 56 if (co1 + co2 <= K) { > 57 best = max(best, double(r1 + r2) / (t1 + > 58 } > 59 if (rat1 <= best && rat2 <= best) > 60 break; > 61 } > 62 } > 63 return best; > 64 } > 65 > 66 void dfs1(int R, int C, int K, const vector<int> &roses, const vector<in > 67 int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL > 68 if (s == 0) { > 69 cand[y*C+x].emplace_back(rr, tt, cc); > 70 return; > 71 } > 72 s--; > 73 rr += roses[y*C + x]; > 74 tt += tulips[y*C + x]; > 75 cc += costs[y*C + x]; > 76 if (y + 1 < R) > 77 dfs1(R, C, K, roses, tulips, costs, y+1, x, s, rr, tt, c > 78 if (x + 1 < C) > 79 dfs1(R, C, K, roses, tulips, costs, y, x+1, s, rr, tt, c > 80 } > 81 void dfs2(int R, int C, int K, const vector<int> &roses, const vector<in > 82 int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL > 83 rr += roses[y*C + x]; > 84 tt += tulips[y*C + x]; > 85 cc += costs[y*C + x]; > 86 if (s == 0) { > 87 cand[y*C+x].emplace_back(rr, tt, cc); > 88 return; > 89 } > 90 s--; > 91 if (y - 1 >= 0) > 92 dfs2(R, C, K, roses, tulips, costs, y - 1, x, s, rr, tt, > 93 if (x - 1 >= 0) > 94 dfs2(R, C, K, roses, tulips, costs, y, x - 1, s, rr, tt, > 95 } > 96 }; > 97 > 98 // BEGIN CUT HERE > 99 #include <ctime> > 100 double start_time; string timer() > 101 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 102 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 103 { os << "{ "; > 104 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 105 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 106 void verify_case(const double& Expected, const double& Received) { > 107 bool ok = (abs(Expected - Received) < 1e-9); > 108 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 109 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 110 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 111 #define END verify_case(_, ProposalOptimization().bestPath(R, C, K, roses, > 112 int main(){ > 113 > 114 CASE(0) > 115 int R = 2; > 116 int C = 2; > 117 int K = 100; > 118 int roses_[] = {0, 2, 3, 0}; > 119 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 120 int tulips_[] = {0, 3, 5, 0}; > 121 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 122 int costs_[] = {0, 70, 80, 0}; > 123 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 124 double _ = 0.6666666666666667; > 125 END > 126 CASE(1) > 127 int R = 2; > 128 int C = 2; > 129 int K = 100; > 130 int roses_[] = {0, 2, 3, 0}; > 131 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 132 int tulips_[] = {0, 3, 5, 0}; > 133 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 134 int costs_[] = {0, 170, 100, 0}; > 135 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 136 double _ = 0.6; > 137 END > 138 CASE(2) > 139 int R = 3; > 140 int C = 3; > 141 int K = 98; > 142 int roses_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0}; > 143 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 144 int tulips_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0}; > 145 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 146 int costs_[] = {0, 33, 33, 33, 33, 33, 33, 33, 0}; > 147 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 148 double _ = -1.0; > 149 END > 150 CASE(3) > 151 int R = 5; > 152 int C = 9; > 153 int K = 622; > 154 int roses_[] = {0, 2, 12, 1, 6, 10, 10, 24, 3, 1, 7, 4, 4, 1, 37, 4, 6, > 155 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 156 int tulips_[] = {0, 4, 37, 22, 3, 14, 10, 6, 5, 6, 5, 17, 4, 7, 12, 3, 1 > 157 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 158 int costs_[] = {0, 19, 70, 79, 18, 43, 49, 65, 16, 38, 61, 69, 43, 12, 6 > 159 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 160 double _ = 2.161290322580645; > 161 END > 162 CASE(4) > 163 int R = 2; > 164 int C = 3; > 165 int K = 15; > 166 int roses_[] = {0, 1, 3, 1, 1, 0}; > 167 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 168 int tulips_[] = {0, 1, 2, 6, 1, 0}; > 169 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 170 int costs_[] = {0, 1, 18, 9, 1, 0}; > 171 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 172 double _ = 1.0; > 173 END > 174 CASE(5) > 175 int R = 17; > 176 int C = 17; > 177 int K = 1000000000; > 178 int roses_[] = { 0,17713,98005,85972,85419,41343,40594,75347,93890,14460 > 179 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 180 int tulips_[] = { 0,9769,3028,85209,31522,29537,15670,9872,74152,90511,3 > 181 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 182 int costs_[] = { 0,66626,71469,70328,62092,18516,71453,8941,94840,56510, > 183 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 184 double _ = -2; > 185 END > 186 /* > 187 CASE(6) > 188 int R = 5; > 189 int C = 60; > 190 int K = 100000000; > 191 int roses_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 > 192 vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); > 193 int tulips_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 194 vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)) > 195 int costs_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 > 196 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 197 double _ = -2; > 198 END > 199 */ > 200 } > 201 // END CUT HERE