#include <bits/stdc++.h> #include "sphinx.h" using namespace std; #define ll long long #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> // Pomocná funkce pro nastavení barev pro experiment // target_color: barva, kterou testujeme // k: modulo posun (0, 1, 2) // l, r: rozsah pro binary search (kde jsou aktivní testy) // ord: seřazené vrcholy cesty // found: indexy, které už jsme pro tuto barvu našli (aby se nepočítaly znovu) void create(int target_color, int k, int n, vector<int>& a, int l, int r, const vector<int>& ord, const set<int>& found){ // Reset na Sphinx barvu (rozpojí vše) fill(a.begin(), a.end(), n); for (int j = 0; j < n - 1; j++) { // Kontrola, zda je tento "most" v aktuálním rozsahu binary searche bool in_range = (j >= l && j <= r); // Pokud už jsme tento bod našli, v experimentu ho ignorujeme (necháme Sphinx), // aby neovlivňoval počty pro hledání dalších. if (found.count(j)) in_range = false; if (j % 3 == k) { // Checkujeme dvojici: ord[j] (Original) -- ord[j+1] (Target Color) // Pokud ord[j] má barvu 'target_color', spojí se s ord[j+1]. // Nastavíme jen pokud jsme v rozsahu if (in_range) { a[ord[j]] = -1; // Original a[ord[j+1]] = target_color; // Fixed color } } } } std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) { int n = N; vector<vector<int>> graf(n); for (int i = 0; i < X.size(); i++) { graf[X[i]].push_back(Y[i]); graf[Y[i]].push_back(X[i]); } // 1. Linearizace cesty (seřazení vrcholů, abychom mohli používat j % 3) vector<int> ord; { int start = 0; for(int i=0; i<n; i++) if(graf[i].size() == 1) { start = i; break; } vector<bool> vis(n, false); int curr = start; while(true){ vis[curr] = true; ord.push_back(curr); bool moved = false; for(int next : graf[curr]){ if(!vis[next]){ curr = next; moved = true; break; } } if(!moved) break; } } vector<int> colors(n, -1); vector<int> a(n); int identified_count = 0; // Iterujeme možné barvy. // Pokud je N velké, spoléháme na to, že součet výskytů všech barev je N, // takže celkový počet kroků BS bude N*logN. for (int i = 0; i < n; i++) { if (identified_count == n) break; // Optimalizace for (int k = 0; k < 3; k++) { set<int> found; // Lambda funkce pro zjištění počtu spojení v intervalu auto get_matches = [&](int l, int r) { create(i, k, n, a, l, r, ord, found); int components = perform_experiment(a); // Spočítáme, kolik dvojic jsme aktivovali int active_pairs = 0; for(int j=l; j<=r; j++) { if (j % 3 == k && !found.count(j) && j < n-1) active_pairs++; } // Každý aktivní pár přidá 2 vrcholy. // Pokud se NESPOJÍ, přispějí 2 komponentami (nebo 1+1). // Pokud se SPOJÍ, počet komponent klesne o 1 oproti očekávání. // Ostatní (Sphinx) jsou izolované komponenty. // Celkem vrcholů = N. Sphinx = N - 2*active. // Expected components (pokud žádná shoda) = (N - 2*active) + 2*active = N. // Každé spojení sníží počet komponent

sphinx.cpp: In lambda function:
sphinx.cpp:95:18: error: expected '}' at end of input
   95 |                 }
      |                  ^
sphinx.cpp:87:50: note: to match this '{'
   87 |             auto get_matches = [&](int l, int r) {
      |                                                  ^
sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:95:18: error: expected ',' or ';' at end of input
   95 |                 }
      |                  ^
sphinx.cpp:95:18: error: expected '}' at end of input
sphinx.cpp:83:37: note: to match this '{'
   83 |         for (int k = 0; k < 3; k++) {
      |                                     ^
sphinx.cpp:95:18: error: expected '}' at end of input
   95 |                 }
      |                  ^
sphinx.cpp:80:33: note: to match this '{'
   80 |     for (int i = 0; i < n; i++) {
      |                                 ^
sphinx.cpp:95:18: error: expected '}' at end of input
   95 |                 }
      |                  ^
sphinx.cpp:42:78: note: to match this '{'
   42 | std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
      |                                                                              ^
sphinx.cpp:95:18: warning: no return statement in function returning non-void [-Wreturn-type]
   95 |                 }
      |                  ^