// Does a BFS on the pairs of locations to find a shortest difference // Additionally exploits reflexivity, symmetry and transitivity (union-find), // O(n alpha(n)) #include #include #include #include using namespace std; // From David Venhoek's TRD vector du_parent; vector du_rank; void init(int n) { du_parent.assign(n,-1); du_rank.assign(n,0); } int find(int k) { if (du_parent[k] == -1) return k; du_parent[k] = find(du_parent[k]); return du_parent[k]; } void dunion(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (du_rank[a] < du_rank[b]) { du_parent[b] = a; } else { du_parent[a] = b; if (du_rank[b] == du_rank[a]) du_rank[b]++; } } struct node { int left, right; bool tower; }; 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; init(n); work.push({{a, b}, 0}); while(!work.empty()){ const auto p = work.front(); work.pop(); if(find(p.first.first) == find(p.first.second)) 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; } dunion(p.first.first, p.first.second); // add next states work.push({{a.left, b.left}, d+1}); work.push({{a.right, b.right}, d+1}); } cout << "indistinguishable" << endl; }