Click Here to go back to the homepage.

Ceiling Function Solution:


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

int main(){
    // #ifndef TESTING
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    
    int nTrees, nNodesPerTree;
    cin >> nTrees >> nNodesPerTree;
    set<string> distinctShapes;
    while(nTrees--){
        map<int, pair<int, int>> tree;
        int layerVal;
        cin >> layerVal;
        int root = layerVal;
        tree.insert({root, {0, 0}});
        for(int i = 1; i < nNodesPerTree; i++){
            cin >> layerVal;
            int tempNode = root;
            map<int, pair<int, int>>::iterator it = tree.find(tempNode);
            while(1){
                if(layerVal < tempNode){
                    it = tree.find((*it).second.first);
                } else{
                    it = tree.find((*it).second.second);
                }
                if(it == tree.end()){
                    break;
                }
                tempNode = (*it).first;
            }
            it = tree.find(tempNode);
            if(layerVal < tempNode){
                (*it).second.first = layerVal;
            } else {
                (*it).second.second = layerVal;
            }
            tree.insert({layerVal, {0, 0}});
        }
        queue<int> q;
        q.push(root);
        string shape = "";
        while(q.size() > 0){
            map<int, pair<int, int>>::iterator it = tree.find(q.front());
            if(it == tree.end()){
                shape.append("|0,0|");
            } else {
                shape.append(string("|") + ((*it).second.first > 0? "L": "0") + "," + ((*it).second.second > 0? "R" : "0") + "|");
                q.push((*it).second.first);
                q.push((*it).second.second);
            }
            q.pop();
        }
        distinctShapes.insert(shape);
    }
    cout << distinctShapes.size() << endl;

    return 0;
}