Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <bitset>
- #include <future>
- #include <functional>
- #define MAX_INT 2147483647
- #define ll long long
- using namespace std;
- int M = 0;
- vector<vector<int>> g;
- vector<bool> used;
- struct comp{
- comp(int _weight = 0){
- weight = _weight;
- }
- int weight;
- };
- void parse_line(const string& str, size_t l, size_t r, vector<int>& GG, array<int,10> int_to_ignore){
- string value;
- vector<int> vec;
- for(;l < r; ++l){
- if(str[l] == ','){
- vec.push_back(stoi(value));
- value = "";
- continue;
- }
- value.push_back(str[l]);
- }
- vec.push_back(stoi(value));
- for(size_t i = 0; i < vec.size(); ++i){
- if(vec[i] == 1 && find(int_to_ignore.begin(),int_to_ignore.end(),i) == int_to_ignore.end()){
- GG.push_back(i);
- }
- }
- }
- void parse_matrix(const string& str, size_t l, size_t r, vector<vector<int>>& G){
- vector<size_t> l_idx, r_idx;
- for(;l < r; ++l){
- if(str[l] == '['){
- l_idx.push_back(l);
- continue;
- }
- if(str[l] == ']'){
- r_idx.push_back(l);
- }
- }
- for(size_t i = 0 ; i < l_idx.size(); ++i){
- G.push_back({});
- array<int,10> int_to_ignore{};
- int_to_ignore.fill(-1);
- int_to_ignore[0] = i;
- parse_line(str,l_idx[i]+1,r_idx[i],G.back(),int_to_ignore);
- }
- }
- void parse(const string& str, vector<vector<int>>& G,int& MM){
- vector<size_t> l_idx, r_idx;
- for(size_t i = 0 ; i < str.size(); ++i){
- if(str[i] == '['){
- l_idx.push_back(i);
- continue;
- }
- if(str[i] == ']'){
- r_idx.push_back(i);
- }
- }
- MM = stoi(string(str.begin()+r_idx.back()+2,str.begin()+r_idx.back()+3));
- parse_matrix(str,l_idx[0]+1,r_idx.back(),G);
- }
- void dfs(int v, comp& C){
- C.weight++;
- used[v] = true;
- for(auto to: g[v]){
- if(!used[to]){
- dfs(to,C);
- }
- }
- }
- int comps(){
- int ans = 0;
- for(int i =0 ; i < used.size(); ++i){
- if(!used[i]){
- comp c;
- dfs(i,c);
- ans += (int)ceil((double)c.weight/M);
- }
- }
- return ans;
- }
- ostream& show_graph(ostream& os){
- for(size_t i = 0; i < g.size(); ++i){
- os << i << ':';
- for(size_t j = 0; j < g[i].size(); ++j){
- os << g[i][j] << ' ';
- }
- os << '\n';
- }
- return os;
- }
- int main(){
- {
- ifstream file_input("test.txt");
- string input;
- getline(cin,input);
- //getline(file_input,input);
- parse(input,g,M);
- }
- used.resize(g.size(), false);
- cout << comps() << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement