Advertisement
OIQ

haha

OIQ
Dec 28th, 2019
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. vector <vector<int>> g;
  9. int index = 1;
  10. int n;
  11. vector<bool> flag;
  12. int counter = 0;
  13. vector<int> a;
  14. int ans = 0;
  15.  
  16. void getline(int i, string& s) {
  17.     int j = 0;
  18.     while (s[index] != ']') {
  19.         if (isdigit(s[index])) {
  20.             if (s[index] == '1')
  21.                 g[i].push_back(j);
  22.             j++;
  23.         }
  24.  
  25.         index++;
  26.     }
  27. }
  28.  
  29. void getvec(string& s, int n) {
  30.  
  31.     for (int i = 0; i < n; i++) {
  32.         getline(i, s);
  33.         index += 3;
  34.     }
  35. }
  36.  
  37. int getlen(string& s) {
  38.  
  39.     int n = 0;
  40.     int ind = 1;
  41.     while (s[ind] != ']') {
  42.         if (isdigit(s[ind]))
  43.             ++n;
  44.         ind++;
  45.  
  46.     }
  47.  
  48.     return n;
  49.  
  50. }
  51.  
  52. void dfs(int v) {
  53.     flag[v] = true;
  54.     ++counter;
  55.     for (int u : g[v]) {
  56.         if (!flag[u] && u != v) {
  57.             dfs(u);
  58.         }
  59.     }
  60. }
  61.  
  62. int main() {
  63.     string s;
  64.     getline(cin, s);
  65.     s = s.substr(2, s.size() - 3);
  66.     int m = s[s.size() - 1] - '0';
  67.     n = getlen(s);
  68.     flag.resize(n);
  69.     g.resize(n);
  70.     s = s.substr(0, s.size() - 3);
  71.     getvec(s, n);
  72.     for (int i = 0; i < n; i++) {
  73.         if (!flag[i]) {
  74.             counter = 0;
  75.             dfs(i);
  76.             if (counter == 1)
  77.                 ++ans;
  78.             else
  79.                 a.push_back(counter);
  80.         }
  81.     }
  82.  
  83.     for (int i = 0; i < a.size(); i++)
  84.         ans += ceil(1.0 * a[i] / m);
  85.    
  86.  
  87.     cout << ans;
  88. }
Advertisement
RAW Paste Data Copied
Advertisement