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;
}