ICPC-T02935: Subway Tree Systems

#include <bits/stdc++.h>
using namespace std;

string sortCode(string &str){
    vector<string> chd;
    string tmp = "";
    int cnt = 0;
    for(int i = 1; i < (int)str.size() - 1; ++i){
        char c = str[i];
        if(c == '0'){
            ++cnt;
        } else {
            --cnt;
        }
        tmp += c;
        if(cnt == 0){
            chd.push_back(sortCode(tmp));
            tmp = "";
        }
    }
    sort(chd.begin(), chd.end());
    string ret = "0";
    for(string &s : chd){
        ret += s;
    }
    return ret + '1';
}

int main(){

    int Q;
    scanf("%d", &Q);
    while(Q--){
        string strA, strB;
        cin >> strA >> strB;
        strA = '0' + strA + '1';
        strB = '0' + strB + '1';
        if(sortCode(strA) == sortCode(strB)){
            cout << "same\n";
        } else {
            cout << "different\n";
        }
    }

    return 0;
}