// Does a BFS on the pairs of locations to find a shortest difference // Additionally exploits reflexivity and symmetry, // Too slow because it is still O(n^2) worst-case #include #include #include #include #include using namespace std; struct pair_hash { inline size_t operator()(const pair & v) const { return (v.first << 14) + v.second; } }; struct node { int left, right; bool tower; }; template pair swap(pair bla) { return {bla.second, bla.first}; } int main(){ int n,a,b; cin >> n >> a >> b; vector graph(n); for(auto & n : graph) { cin >> n.left >> n.right >> n.tower; } // ((A, B), distance) queue, int>> work; unordered_set, pair_hash> visited; work.push({{a, b}, 0}); while(!work.empty()){ const auto p = work.front(); work.pop(); // check reflexivity if(p.first.first == p.first.second) continue; // check symmetry if(visited.count(p.first) > 0) continue; if(visited.count(swap(p.first)) > 0) continue; const auto d = p.second; const auto & a = graph[p.first.first]; const auto & b = graph[p.first.second]; if(a.tower != b.tower) { cout << d << endl; return 0; } visited.insert(p.first); // add next states work.push({{a.left, b.left}, d+1}); work.push({{a.right, b.right}, d+1}); } cout << "indistinguishable" << endl; }