I'm trying to solve https://open.kattis.com/problems/animal. My code can be found here : http://pastebin.com/xgXiDj91. I'm new to competitive programming and C++ in general. Having said this, my approach is to parse the input string [ e.g. ((3,(1,(5,2))),4) ] into a list [ ((3(1(52)))4) ]. After that i note all elements, split it into the two subtrees and add both back to a queue, starting over again, until there is nothing to split anymore. Afterwards i compare the two sets i obtained this way. If i am not mistaken this should lead to a complexity of O(Nlog(N)), since for every subtree, i need to collect all elements that belong to it, which would amount to Nlog(N) in a complete binary tree. This works for the provided test sets, but exceeds the time limit on the submission.

Could you please help me figure out where i can improve my code and what i did inefficiently?

I'm new to competitive programming and C++ in general. I have solved the Kattis Animal Classification challenge. We are given two classification trees, each represented using nested parentheses. For example, ((3,(1,(5,2))),4) and (((5,1),(2,3)),4) represent the trees

   ╱╲                   ╱╲
  ╱╲ 4                 ╱╲ 4
 ╱ ╱╲                 ╱  ╲
3 1 ╱╲               ╱╲  ╱╲
   5  2             5 1  2 3

The challenge is to report the fact that there are 7 subgroups in common between the two trees (namely {1}, {2}, {3}, {4}, {5}, {1,2,3,5}, and {1,2,3,4,5}).

My approach is to parse the input string [ e.g. ((3,(1,(5,2))),4) ] into a list [ ((3(1(52)))4) ]. After that I note all elements, split it into the two subtrees and add both back to a queue, starting over again, until there is nothing to split anymore. Afterwards i compare the two sets i obtained this way. If i am not mistaken this should lead to a complexity of O(N log(N)), since for every subtree, i need to collect all elements that belong to it, which would amount to N log(N) in a complete binary tree. This works for the provided test sets, but exceeds the time limit on the submission.

Could you please help me figure out where I can improve my code and what I did inefficiently?

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <deque>

using namespace std; 


struct hash_X{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int element: x){sum = sum+element;}
    return sum;
  }
};

unordered_set<unordered_set<int>, hash_X> get_sets(list<string> L){
    unordered_set<unordered_set<int>, hash_X> subsets;
    list<string> K;
    deque<list<string>> Q;
    Q.push_back(L);
    while(not Q.empty()){
        K = Q.back();
        Q.pop_back();
    //K is of the form for example (x(yz)), so we start by getting the set of all elements tmp = {x,y,z} and adding it to the result. afterwards we unwrap ~ x(yz) and split into the two subtrees x and (yz)
    //and add both to the queue. If only one node is left ( x ) we dont add it back to the queue
        unordered_set<int> subset;
        for(string s: K){
        if( s!="(" and s!=")" ){
            int i = stoi(s); 
            subset.insert(i);
        }
    }
        subsets.insert(subset);
        if(K.size() >= 2){
        //Here we split K into the left and right subtree, modifying K inplace to save some time.. hopefully!
            K.pop_front();
            K.pop_back();
            list<string>::iterator it = K.begin();
            if(*it == "("){
                int i = 1;
                while(i != 0){
                    it++;
                    if(*it == ")"){i = i-1;}
                    else if(*it == "("){i=i+1;}
                 }
            }
            it++;
            list<string> right;
            list<string>::iterator it_right = right.begin();
            right.splice(it_right, K, it, K.end());
            Q.push_front(K);
            Q.push_front(right);
        }
    }
    return subsets;
}


int main(){
    int n;
    cin >> n;
    //input stuff
    string inputA, inputB;
    cin >> inputA; 
    cin >> inputB;
    // parse "((3,(1,(5,2))),4)" into ((3(1(52)))4)
    list<string> A, B;
    for(int i = 0; i < inputA.size(); i++){
        string c = "";
    c += inputA[i];
        if( c == "(" or c == ")" ){A.push_back(c);}
        else if( isdigit(inputA[i]) ){
            string tmp = "";
            while( isdigit(inputA[i]) ){
                tmp += inputA[i];
                i++;
            }
            i--;
            A.push_back(tmp);
        }
    }
    for(int i = 0; i <= inputB.size(); i++){
        string c = "";
        c += inputB[i];
        if( c == "(" or c == ")" ){B.push_back(c);}
        else if( isdigit(inputB[i]) ){
            string tmp = "";
            while( isdigit(inputB[i]) ){
                tmp += inputB[i];
                i++;
            }
            i--;
            B.push_back(tmp);
        }
    }

    // make the trees and get the subsets.
    unordered_set<unordered_set<int>, hash_X> setsA = get_sets(A);
    unordered_set<unordered_set<int>, hash_X> setsB = get_sets(B);
    int res = count_if(setsB.begin(), setsB.end(), [&](unordered_set<int> subsetofB) {return setsA.find(subsetofB) != setsB.end();});
    cout << res;
}

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <deque>

using namespace std; 


struct hash_X{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int i: x){sum = sum+i;}
    return sum;
  }
};

unordered_set<unordered_set<int>, hash_X> mt(list<string> L){
    unordered_set<unordered_set<int>, hash_X> S;
    list<string> K;
    deque<list<string>> Q;
    Q.push_back(L);
    while(not Q.empty()){
    K = Q.back();
    unordered_set<int> tmp;
    for(string s: K){if( s!="(" and s!=")" ){int i = stoi(s); tmp.insert(i);}}
    S.insert(tmp);
    //K is of the form for example (x(yz)), so first we unwrap ~ x(yz) and split into the two subtrees x and (yz)
    //and add both to the queue. If only one node is left ( x ) we dont add it back to the queue
    if(K.size() >= 2){
        K.pop_front();
        K.pop_back();
        list<string>::iterator it = K.begin();
        if(*it == "("){
            int i = 1;
            while(i != 0){
                it++;
                if(*it == ")"){i = i-1;}
                else if(*it == "("){i=i+1;}
                }
            }
        it++;
        list<string> B;
        list<string>::iterator itB = B.begin();
        B.splice(itB, K, it, K.end());
        Q.push_front(K);
        Q.push_front(B);
    }
    Q.pop_back();
    }
    return S;
}


int main(){
    int n;
    string x, y;
    char c;
    list<string> A, B;
    cin >> n;
    cin.ignore();
    cin >> x; 
    cin >> y;
    // parse "((3,(1,(5,2))),4)" into ((3(1(52)))4)
    for(int i = 0; i < x.size(); i++){
    string c = "";
    c += x[i];
    if( c == "(" or c == ")" ){A.push_back(c);}
    if( isdigit(x[i]) ){
        string tmp = "";
        while( isdigit(x[i]) ){
            tmp += x[i];
            i++;
        }
        i--;
        A.push_back(tmp);
    }
    }
    for(int i = 0; i <= y.size(); i++){
    string c = "";
    c += y[i];
    if( c == "(" or c == ")" ){B.push_back(c);}
    if( isdigit(y[i]) ){
        string tmp = "";
        while( isdigit(y[i]) ){
            tmp += y[i];
            i++;
        }
        i--;
        B.push_back(tmp);
    }
    }

    // make the trees
    unordered_set<unordered_set<int>, hash_X> t1 = mt(A);
    unordered_set<unordered_set<int>, hash_X> t2 = mt(B);
    unordered_set<unordered_set<int>, hash_X> i(t1.begin(), t1.end());
    int res = count_if(t2.begin(), t2.end(), [&](unordered_set<int> k) {return i.find(k) != i.end();});
    cout << res;
}

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <deque>

using namespace std; 


struct hash_X{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int i: x){sum = sum+i;}
    return sum;
  }
};

unordered_set<unordered_set<int>, hash_X> mt(list<string> L){
    unordered_set<unordered_set<int>, hash_X> S;
    list<string> K;
    deque<list<string>> Q;
    Q.push_back(L);
    while(not Q.empty()){
    K = Q.back();
    unordered_set<int> tmp;
    for(string s: K){if( s!="(" and s!=")" ){int i = stoi(s); tmp.insert(i);}}
    S.insert(tmp);
    //K is of the form for example (x(yz)), so first we unwrap ~ x(yz) and split into the two subtrees x and (yz)
    //and add both to the queue. If only one node is left ( x ) we dont add it back to the queue
    if(K.size() >= 2){
        K.pop_front();
        K.pop_back();
        list<string>::iterator it = K.begin();
        if(*it == "("){
            int i = 1;
            while(i != 0){
                it++;
                if(*it == ")"){i = i-1;}
                else if(*it == "("){i=i+1;}
                }
            }
        it++;
        list<string> B;
        list<string>::iterator itB = B.begin();
        B.splice(itB, K, it, K.end());
        Q.push_front(K);
        Q.push_front(B);
    }
    Q.pop_back();
    }
    return S;
}


int main(){
    int n;
    string x, y;
    char c;
    list<string> A, B;
    cin >> n;
    cin.ignore();
    cin >> x; 
    cin >> y;
    // parse "((3,(1,(5,2))),4)" into ((3(1(52)))4)
    for(int i = 0; i < x.size(); i++){
    string c = "";
    c += x[i];
    if( c == "(" or c == ")" ){A.push_back(c);}
    if( isdigit(x[i]) ){
        string tmp = "";
        while( isdigit(x[i]) ){
            tmp += x[i];
            i++;
        }
        i--;
        A.push_back(tmp);
    }
    }
    for(int i = 0; i <= y.size(); i++){
    string c = "";
    c += y[i];
    if( c == "(" or c == ")" ){B.push_back(c);}
    if( isdigit(y[i]) ){
        string tmp = "";
        while( isdigit(y[i]) ){
            tmp += y[i];
            i++;
        }
        i--;
        B.push_back(tmp);
    }
    }

    // make the trees
    unordered_set<unordered_set<int>, hash_X> t1 = mt(A);
    unordered_set<unordered_set<int>, hash_X> t2 = mt(B);
    unordered_set<unordered_set<int>, hash_X> i(t1.begin(), t1.end());
    int res = count_if(t2.begin(), t2.end(), [&](unordered_set<int> k) {return i.find(k) != i.end();});
    cout << res;
}

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <deque>

using namespace std; 


struct hash_X{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int element: x){sum = sum+element;}
    return sum;
  }
};

unordered_set<unordered_set<int>, hash_X> get_sets(list<string> L){
    unordered_set<unordered_set<int>, hash_X> subsets;
    list<string> K;
    deque<list<string>> Q;
    Q.push_back(L);
    while(not Q.empty()){
        K = Q.back();
        Q.pop_back();
    //K is of the form for example (x(yz)), so we start by getting the set of all elements tmp = {x,y,z} and adding it to the result. afterwards we unwrap ~ x(yz) and split into the two subtrees x and (yz)
    //and add both to the queue. If only one node is left ( x ) we dont add it back to the queue
        unordered_set<int> subset;
        for(string s: K){
        if( s!="(" and s!=")" ){
            int i = stoi(s); 
            subset.insert(i);
        }
    }
        subsets.insert(subset);
        if(K.size() >= 2){
        //Here we split K into the left and right subtree, modifying K inplace to save some time.. hopefully!
            K.pop_front();
            K.pop_back();
            list<string>::iterator it = K.begin();
            if(*it == "("){
                int i = 1;
                while(i != 0){
                    it++;
                    if(*it == ")"){i = i-1;}
                    else if(*it == "("){i=i+1;}
                 }
            }
            it++;
            list<string> right;
            list<string>::iterator it_right = right.begin();
            right.splice(it_right, K, it, K.end());
            Q.push_front(K);
            Q.push_front(right);
        }
    }
    return subsets;
}


int main(){
    int n;
    cin >> n;
    //input stuff
    string inputA, inputB;
    cin >> inputA; 
    cin >> inputB;
    // parse "((3,(1,(5,2))),4)" into ((3(1(52)))4)
    list<string> A, B;
    for(int i = 0; i < inputA.size(); i++){
        string c = "";
    c += inputA[i];
        if( c == "(" or c == ")" ){A.push_back(c);}
        else if( isdigit(inputA[i]) ){
            string tmp = "";
            while( isdigit(inputA[i]) ){
                tmp += inputA[i];
                i++;
            }
            i--;
            A.push_back(tmp);
        }
    }
    for(int i = 0; i <= inputB.size(); i++){
        string c = "";
        c += inputB[i];
        if( c == "(" or c == ")" ){B.push_back(c);}
        else if( isdigit(inputB[i]) ){
            string tmp = "";
            while( isdigit(inputB[i]) ){
                tmp += inputB[i];
                i++;
            }
            i--;
            B.push_back(tmp);
        }
    }

    // make the trees and get the subsets.
    unordered_set<unordered_set<int>, hash_X> setsA = get_sets(A);
    unordered_set<unordered_set<int>, hash_X> setsB = get_sets(B);
    int res = count_if(setsB.begin(), setsB.end(), [&](unordered_set<int> subsetofB) {return setsA.find(subsetofB) != setsB.end();});
    cout << res;
}