#include "sphinx.h" #include <bits/stdc++.h> using namespace std; bool BEGIN_ALLOC; #define FOR(i, l, r) for(int i = (l); i < (r); ++i) #define F0R(i, r) FOR(i, 0, r) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define ff first #define ss second #define mp make_pair #define mt make_tuple #define tcT template<class T tcT> bool minimize(T& a, const T& b){ return (a > b ? a = b, 1 : 0); } tcT> bool maximize(T& a, const T& b){ return (a < b ? a = b, 1 : 0); } using ll = long long; using db = double; using ull = unsigned long long; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vpi = vector<pi>; using vpl = vector<pl>; map<vi, int> askedQueries; int query(vi E){ if(askedQueries.count(E)) return askedQueries[E]; return askedQueries[E] = perform_experiment(E); } vi find_colours12(int N, vi X, vi Y){ vi base(N, -1); vi ans(N); F0R(i, N){ vi p(N); iota(all(p), 0); shuffle(all(p), mt19937(12310123123)); for(auto c : p){ fill(all(base), c); base[i] = -1; if(query(base) == 1){ ans[i] = c; break; } } } return ans; } std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) { // if(N <= 50) return find_colours12(N, X, Y); vector<vi> adj(N); int M = sz(X); F0R(i, M){ adj[X[i]].eb(Y[i]); adj[Y[i]].eb(X[i]); } //Step 1 : Detect monochromatic components vector<vi> components; vi insertOrder(N); iota(all(insertOrder), 0); shuffle(all(insertOrder), mt19937(10210312)); vi vis(N); function<void(int, vi&)> dfs = [&](int u, vi& E){ vis[u] = true; for(auto v : adj[u]) if(!vis[v] && E[v] == N){ dfs(v, E); } }; auto countAdjacentNComponents = [&](int start, vi& E){ fill(all(vis), false); int cnt = 0; for(auto i : adj[start]) if(!vis[i] && E[i] == N){ ++cnt; dfs(i, E); } return cnt; }; auto countNComponents = [&](vi& E){ fill(all(vis), false); int cnt = 0; F0R(i, N) if(!vis[i] && E[i] == N){ ++cnt; dfs(i, E); } return cnt; }; auto countKnownComponents = [&](vi& E){ // cerr << "countKnownComps : \n"; // for(auto u : E) cerr << u << " "; cerr << '\n'; // cerr << '\n'; fill(all(vis), false); int cnt = 0; F0R(i, N) if(!vis[i] && E[i] != -1){ function<void(int)> rec = [&](int u){ vis[u] = true; for(auto v : adj[u]) if(!vis[v] && E[v] == E[i]){ rec(v); } }; ++cnt; rec(i); } // cerr << "== " << cnt << '\n'; return cnt; }; for(auto u : insertOrder){ if(components.empty()){ vi nw = {u}; components.eb(nw); continue; } auto check = [&](int l, int r){ vi E(N, N); FOR(i, l, r + 1){ for(auto u : components[i]) E[u] = -1; } int base = countNComponents(E) + (r - l + 1); E[u] = -1; int cnt = countAdjacentNComponents(u, E); int added = query(E); int ifNew = base + cnt; return ifNew != added; }; vi marked(sz(components)), mergedComponent = {u}; int l = 0, r = sz(components) - 1; while(l <= r && check(l, r)){ int backEdge = -1; int lo = l, hi = r; while(lo <= hi){ int mid = lo + hi >> 1; bool ok = check(l, mid); // cerr << mid << " : " << ok << '\n'; if(ok) backEdge = mid, hi = mid - 1; else lo = mid + 1; } if(backEdge == -1) break; marked[backEdge] = 1; mergedComponent.insert(mergedComponent.end(), all(components[backEdge])); l = backEdge + 1; } vector<vi> newComponents; F0R(i, sz(components)) if(!marked[i]){ newComponents.pb(components[i]); } newComponents.pb(mergedComponent); swap(components, newComponents); } // cerr << "! " << sz(components) << '\n'; // for(auto comp : components){ // for(auto u : comp) cerr << u << ' '; // cerr << '\n'; // } // cerr << '\n'; int cnt = 0; //Compress the monochromatic components into super-vertexes and create the induced graph G' //In G', every edge (u, v) has the property C[u] != C[v] (u, v are both super-vertexes) vi superVertexIdx(N); for(auto comp : components){ for(auto u : comp) superVertexIdx[u] = cnt; ++cnt; } int superNodes = sz(components); vector<vi> adjSuper(superNodes); F0R(i, M){ int x = X[i], y = Y[i]; x = superVertexIdx[x]; y = superVertexIdx[y]; if(x != y){ adjSuper[x].eb(y); adjSuper[y].eb(x); } } vi dist(superNodes, -1); dist[0] = 0; queue<int> q; q.push(0); //Group by distances vi A, B; while(!q.empty()){ int u = q.front(); q.pop(); (dist[u] ? B : A).pb(u); for(auto v : adjSuper[u]) if(dist[v] == -1){ dist[v] = dist[u] ^ 1; q.push(v); } } //Step 2 : Detect original colors auto colorSupervertex = [&](vi& E, int u, int c){ // cerr << "color " << u << ' ' << c << '\n'; for(auto x : components[u]) E[x] = c; }; vi ans(N); F0R(_, 2){ // cerr << "\nthis turn\n"; // cerr << "A = "; for(auto u : A) cerr << u << ' '; cerr << '\n'; // cerr << "B = "; for(auto u : B) cerr << u << ' '; cerr << '\n'; F0R(x, N){ // cerr << "current = " << x << '\n'; vi E(N, -1); for(auto u : B) colorSupervertex(E, u, x); auto check = [&](int l, int r){ // cerr << "check " << l << ' ' << r << '\n'; vi tmp = E; F0R(i, l) colorSupervertex(tmp, A[i], N); FOR(i, r + 1, sz(A)) colorSupervertex(tmp, A[i], N); int cur = query(tmp); int bound = countKnownComponents(tmp); // for(auto x : tmp) cerr << x << ' '; cerr << '\n'; // cerr << "=> " << cur << " | " << bound + (r - l + 1) << '\n'; return cur != (bound + r - l + 1); }; int l = 0, r = sz(A) - 1; while(l <= r && check(l, r)){ // if(l == 0){ // cerr << "A has color " << x << '\n'; // } int lo = l, hi = r, first = -1; while(lo <= hi){ int mid = lo + hi >> 1; if(check(l, mid)) first = mid, hi = mid - 1; else lo = mid + 1; } if(first == -1) break; for(auto u : components[A[first]]){ ans[u] = x; // cerr << "declare that " << u << " has color = " << x << '\n'; } l = first + 1; } // cerr << '\n'; } swap(A, B); // cerr << '\n'; } return ans; }