#include <bits/stdc++.h> #include "sphinx.h" using namespace std; std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) { int n = N; // 1. Linearizace grafu (převedení na cestu) vector<vector<int>> adj(n); for (size_t i = 0; i < X.size(); i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } vector<int> ord; // Pořadí vrcholů na cestě { vector<bool> vis(n, false); int start_node = 0; for (int i = 0; i < n; i++) if (adj[i].size() == 1) { start_node = i; break; } int curr = start_node; while (true) { vis[curr] = true; ord.push_back(curr); bool found = false; for (int neighbor : adj[curr]) { if (!vis[neighbor]) { curr = neighbor; found = true; break; } } if (!found) break; } } vector<int> colors(n, -1); vector<int> a(n); // 2. Hlavní smyčka: Iterujeme přes barvy, které hledáme for (int c = 0; c < n; c++) { // Pro každou barvu projdeme tři možná posunutí (modulo 3), aby se páry nepřekrývaly for (int k = 0; k < 3; k++) { // Helper funkce: Spočítá shody v podmnožině kandidátů // candidates: seznam indexů 'j', které testujeme // l, r: rozsah v poli candidates (ne v grafu!) auto count_matches = [&](const vector<int>& candidates, int l, int r) { if (l > r) return 0; // Reset na Sphinx barvu (N) fill(a.begin(), a.end(), n); int active_cnt = 0; for (int i = l; i <= r; i++) { int j = candidates[i]; // Testujeme pár: ord[j] (original) -- ord[j+1] (barva c) a[ord[j]] = -1; a[ord[j+1]] = c; active_cnt++; } if (active_cnt == 0) return 0; // Každé úspěšné spojení sníží počet komponent o 1 oproti očekávání // Očekávaný počet (pokud se nic nespojí) = N // Počet komponent = N - matches int matches = n - perform_experiment(a); return matches; }; // Smyčka pro nalezení všech výskytů barvy c v aktuálním posunu k while (true) { // Vytvoříme seznam validních kandidátů pro tento krok // Kandidát je index 'j', kde j%3==k a barvu ord[j] ještě neznáme vector<int> candidates; for (int j = k; j < n - 1; j += 3) { if (colors[ord[j]] == -1) { candidates.push_back(j); } } if (candidates.empty()) break; // Rychlý check: je vůbec v celém seznamu kandidátů nějaká shoda? int total = count_matches(candidates, 0, candidates.size() - 1); if (total == 0) break; // Žádná další shoda pro barvu 'c' a posun 'k' // Binary search: hledáme PRVNÍ index v candidates, který způsobí spojení int l = 0, r = candidates.size() - 1; int found_idx_in_candidates = -1; while (l <= r) { if (l == r) { found_idx_in_candidates = l; break; } int mid = l + (r - l) / 2; // Pokud je shoda v levé polovině, jdeme doleva if (count_matches(candidates, l, mid) > 0) { r = mid; } else { l = mid + 1; } } if (found_idx_in_candidates != -1) { int real_j = candidates[found_idx_in_candidates]; colors[ord[real_j]] = c; // Našli jsme barvu! // Cyklus pokračuje (while true), znovu sestaví kandidáty (bez tohoto j) a hledá další } else { break; } } } } // 3. Dořešení posledního vrcholu (ord[n-1]) // Protože hlavní smyčka testuje páry (j, j+1), nikdy nezjistí barvu pro j = n-1. // Jednoduše projdeme barvy a zkusíme ho spojit s předposledním vrcholem. // Toto stojí max N dotazů, což se do limitu 2750 vejde (N <= 250). if (colors[ord[n - 1]] == -1) { for (int c = 0; c < n; c++) { fill(a.begin(), a.end(), n); // Nastavíme předposlední na 'c', poslední na -1 a[ord[n - 2]] = c; a[ord[n - 1]] = -1; // Pokud se spojí, počet komponent bude < N if (perform_experiment(a) < n) { colors[ord[n - 1]] = c; break; } } } // Fallback: Pokud něco zůstalo -1 (nemělo by), nastavíme na 0 for(int i=0; i<n; i++) if(colors[i] == -1) colors[i] = 0; return colors; }