Advertisement
EWTD

Untitled

Dec 13th, 2019
609
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.00 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. #include <iostream>
  4. #include <fstream>
  5. #include <cmath>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <map>
  9. #include <set>
  10. #include <bitset>
  11. #include <future>
  12. #include <functional>
  13. #define MAX_INT 2147483647
  14. #define ll long long
  15. using namespace std;
  16. int M = 0;
  17. vector<vector<int>> g;
  18. vector<bool> used;
  19. struct comp{
  20. comp(int _weight = 0){
  21. weight = _weight;
  22. }
  23. int weight;
  24. };
  25. void parse_line(const string& str, size_t l, size_t r, vector<int>& GG, array<int,10> int_to_ignore){
  26. string value;
  27. vector<int> vec;
  28. for(;l < r; ++l){
  29. if(str[l] == ','){
  30. vec.push_back(stoi(value));
  31. value = "";
  32. continue;
  33. }
  34. value.push_back(str[l]);
  35. }
  36. vec.push_back(stoi(value));
  37. for(size_t i = 0; i < vec.size(); ++i){
  38. if(vec[i] == 1 && find(int_to_ignore.begin(),int_to_ignore.end(),i) == int_to_ignore.end()){
  39. GG.push_back(i);
  40. }
  41. }
  42. }
  43. void parse_matrix(const string& str, size_t l, size_t r, vector<vector<int>>& G){
  44. vector<size_t> l_idx, r_idx;
  45. for(;l < r; ++l){
  46. if(str[l] == '['){
  47. l_idx.push_back(l);
  48. continue;
  49. }
  50. if(str[l] == ']'){
  51. r_idx.push_back(l);
  52. }
  53. }
  54. for(size_t i = 0 ; i < l_idx.size(); ++i){
  55. G.push_back({});
  56. array<int,10> int_to_ignore{};
  57. int_to_ignore.fill(-1);
  58. int_to_ignore[0] = i;
  59. parse_line(str,l_idx[i]+1,r_idx[i],G.back(),int_to_ignore);
  60. }
  61. }
  62. void parse(const string& str, vector<vector<int>>& G,int& MM){
  63. vector<size_t> l_idx, r_idx;
  64. for(size_t i = 0 ; i < str.size(); ++i){
  65. if(str[i] == '['){
  66. l_idx.push_back(i);
  67. continue;
  68. }
  69. if(str[i] == ']'){
  70. r_idx.push_back(i);
  71. }
  72. }
  73. MM = stoi(string(str.begin()+r_idx.back()+2,str.begin()+r_idx.back()+3));
  74. parse_matrix(str,l_idx[0]+1,r_idx.back(),G);
  75. }
  76. void dfs(int v, comp& C){
  77. C.weight++;
  78. used[v] = true;
  79. for(auto to: g[v]){
  80. if(!used[to]){
  81. dfs(to,C);
  82. }
  83. }
  84. }
  85.  
  86. int comps(){
  87. int ans = 0;
  88. for(int i =0 ; i < used.size(); ++i){
  89. if(!used[i]){
  90. comp c;
  91. dfs(i,c);
  92. ans += (int)ceil((double)c.weight/M);
  93. }
  94. }
  95. return ans;
  96. }
  97. ostream& show_graph(ostream& os){
  98. for(size_t i = 0; i < g.size(); ++i){
  99. os << i << ':';
  100. for(size_t j = 0; j < g[i].size(); ++j){
  101. os << g[i][j] << ' ';
  102. }
  103. os << '\n';
  104. }
  105. return os;
  106. }
  107. int main(){
  108. {
  109. ifstream file_input("test.txt");
  110. string input;
  111. getline(cin,input);
  112. //getline(file_input,input);
  113. parse(input,g,M);
  114. }
  115. used.resize(g.size(), false);
  116. cout << comps() << '\n';
  117. return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement