Submission #1229625

#TimeUsernameProblemLanguageResultExecution timeMemory
1229625boris_mihov스핑크스 (IOI24_sphinx)C++20
3 / 100
1572 ms840 KiB
#include "sphinx.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> #include <set> typedef long long llong; const int MAXN = 250 + 10; const int INF = 1e9; int n, m; int color[MAXN]; struct DSU { int par[MAXN]; std::vector <int> inComponent[MAXN]; void build() { for (int i = 1 ; i <= n ; ++i) { par[i] = i; inComponent[i].push_back(i); } } int find(int node) { if (par[node] == node) return node; return par[node] = find(par[node]); } void connect(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } if (inComponent[u].size() > inComponent[v].size()) { std::swap(u, v); } par[u] = v; for (const int &x : inComponent[u]) { inComponent[v].push_back(x); } } bool areConnected(int u, int v) { return find(u) == find(v); } }; struct DSU2 { int par[MAXN]; int dep[MAXN]; void build() { for (int i = 1 ; i <= n ; ++i) { par[i] = i; dep[i] = 1; } } int find(int node) { if (par[node] == node) return node; return par[node] = find(par[node]); } void connect(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } if (dep[u] > dep[v]) { std::swap(u, v); } if (dep[u] == dep[v]) { dep[v]++; } par[u] = v; } bool areConnected(int u, int v) { return find(u) == find(v); } }; DSU dsu; DSU2 dsuQuery; bool isActive[MAXN]; bool inQueue[MAXN]; std::vector <int> g[MAXN]; std::vector <int> diffGraph[MAXN]; std::vector <int> t[MAXN]; int edgeFrom[MAXN * MAXN]; std::vector <int> part[2]; int edgeTo[MAXN * MAXN]; bool wasSeen[MAXN]; int bigColor[MAXN]; int depth[MAXN]; int answer[MAXN]; bool doneMerging = false; int getWorstCase() { dsuQuery.build(); for (int i = 1 ; i <= m ; ++i) { if (dsu.areConnected(edgeFrom[i], edgeTo[i]) || (color[edgeFrom[i]] != -1 && color[edgeTo[i]] != -1 && color[edgeFrom[i]] == color[edgeTo[i]])) { dsuQuery.connect(edgeFrom[i], edgeTo[i]); } } int res = 0; std::fill(wasSeen, wasSeen + n + 1, 0); for (int i = 1 ; i <= n ; ++i) { res += !wasSeen[dsuQuery.find(i)]; wasSeen[dsuQuery.find(i)] = true; } return res; } int query() { std::vector <int> exp_col(n); for (int i = 1 ; i <= n ; ++i) { exp_col[i - 1] = color[i]; } return perform_experiment(exp_col); } int bigWorstCase() { dsuQuery.build(); for (int i = 1 ; i <= m ; ++i) { if (dsu.areConnected(edgeFrom[i], edgeTo[i]) || (bigColor[dsu.find(edgeFrom[i])] != -1 && bigColor[dsu.find(edgeTo[i])] != -1 && bigColor[dsu.find(edgeFrom[i])] == bigColor[dsu.find(edgeTo[i])])) { dsuQuery.connect(edgeFrom[i], edgeTo[i]); } } int res = 0; std::fill(wasSeen, wasSeen + n + 1, 0); for (int i = 1 ; i <= n ; ++i) { res += !wasSeen[dsuQuery.find(i)]; wasSeen[dsuQuery.find(i)] = true; } return res; } int bigQuery() { std::vector <int> exp_col(n); for (int i = 1 ; i <= n ; ++i) { exp_col[i - 1] = bigColor[dsu.find(i)]; } // std::cout << " call query\n"; // std::cout << " "; for (const int &u : exp_col) std::cout << u << ' '; std::cout << '\n'; return perform_experiment(exp_col); } std::vector <int> find_colours(int N, std::vector <int> X, std::vector <int> Y) { n = N; m = X.size(); for (int i = 0 ; i < m ; ++i) { X[i]++; Y[i]++; edgeFrom[i + 1] = X[i]; edgeTo[i + 1] = Y[i]; g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } std::fill(color + 1, color + 1 + n, n); dsu.build(); std::queue <int> q; inQueue[1] = true; q.push(1); while (q.size()) { int node = q.front(); q.pop(); isActive[node] = true; std::set <int> set; for (const int &u : g[node]) { if (isActive[u]) { set.insert(dsu.find(u)); } } std::fill(color + 1, color + 1 + n, n); for (const int &comp : set) { for (const int &u : dsu.inComponent[comp]) { color[u] = -1; } } color[node] = -1; int cnt = getWorstCase(); int res = query(); int diff = cnt - res; int oldR = -1; while (diff--) { assert(set.size()); std::vector <int> vals; for (const int &comp : set) { vals.push_back(comp); } int l = oldR, r = (int)vals.size() - 1, mid; while (l < r - 1) { mid = l + r >> 1; std::fill(color + 1, color + 1 + n, n); for (int i = 0 ; i <= mid ; ++i) { for (const int &u : dsu.inComponent[vals[i]]) { color[u] = -1; } } color[node] = -1; cnt = getWorstCase(); res = query(); if (res == cnt) l = mid; else r = mid; } dsu.connect(node, vals[r]); oldR = r; } for (const int &u : g[node]) { if (!inQueue[u]) { inQueue[u] = true; q.push(u); } } } std::set <std::pair <int,int>> added_edges; for (int i = 0 ; i < m ; ++i) { if (dsu.find(X[i]) != dsu.find(Y[i]) && !added_edges.count({dsu.find(X[i]), dsu.find(Y[i])})) { added_edges.insert({dsu.find(X[i]), dsu.find(Y[i])}); added_edges.insert({dsu.find(Y[i]), dsu.find(X[i])}); diffGraph[dsu.find(X[i])].push_back(dsu.find(Y[i])); diffGraph[dsu.find(Y[i])].push_back(dsu.find(X[i])); } } bool allEqual = true; for (int i = 2 ; i <= n ; ++i) { if (!dsu.areConnected(1, i)) { allEqual = false; break; } } if (allEqual) { for (int c = 0 ; c < N ; ++c) { std::vector <int> toQuery(n, -1); toQuery[0] = c; if (perform_experiment(toQuery) != n) { return std::vector <int> (n, c); } } assert(false); } std::fill(inQueue, inQueue + 1 + n, 0); inQueue[dsu.find(1)] = true; q.push(dsu.find(1)); part[0].push_back(dsu.find(1)); while (q.size()) { int node = q.front(); q.pop(); for (const int &v : dsu.inComponent[node]) { for (const int &u : g[v]) { if (!inQueue[dsu.find(u)]) { depth[dsu.find(u)] = depth[node] + 1; part[depth[dsu.find(u)] & 1].push_back(dsu.find(u)); t[node].push_back(dsu.find(u)); inQueue[u] = true; q.push(dsu.find(u)); } } } } // std::cout << "merged\n"; // for (int i = 1 ; i <= n ; ++i) // { // std::cout << i << ": " << dsu.find(i) << '\n'; // } // std::cout << "parts\n"; // for (const int &u : part[0]) std::cout << u << ' '; std::cout << '\n'; // for (const int &u : part[1]) std::cout << u << ' '; std::cout << '\n'; for (int times = 0 ; times < 2 ; ++times) // curr -> 0; other -> 1 { // std::cout << "times: " << times << '\n'; std::vector <int> found; for (int c = 0 ; c < N ; ++c) { for (const int &u : part[0]) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = -1; } } for (const int &u : part[1]) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = c; } } for (const int &u : found) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = answer[v]; } } int cnt = bigWorstCase(); int res = bigQuery(); // std::cout << "for c: " << c << ' ' << cnt << ' ' << res << '\n'; bool shouldEnd = (cnt == res); int lastR = -1; while (!shouldEnd) { // std::cout << "to binary: " << lastR << '\n'; // for (const int &u : part[0]) std::cout << u << ' '; std::cout << '\n'; int resultR = -1; int l = lastR, r = part[0].size(), mid; while (l < r - 1) { mid = l + r >> 1; // std::cout << "binary: " << mid << '\n'; std::fill(bigColor + 1, bigColor + 1 + n, n); for (const int &u : part[1]) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = c; } } for (int i = 0 ; i <= mid ; ++i) { for (const int &v : dsu.inComponent[part[0][i]]) { bigColor[v] = -1; } } for (const int &u : found) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = answer[v]; } } cnt = bigWorstCase(); res = bigQuery(); if (cnt == res) l = mid; else { r = mid; resultR = res; } } // std::cout << "find: " << part[0][r] << ' ' << c << '\n'; found.push_back(part[0][r]); answer[part[0][r]] = c; lastR = r; for (const int &u : part[0]) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = -1; } } for (const int &u : part[1]) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = c; } } for (const int &u : found) { for (const int &v : dsu.inComponent[u]) { bigColor[v] = answer[v]; } } cnt = bigWorstCase(); shouldEnd = (cnt == resultR); } } std::swap(part[0], part[1]); } std::vector <int> sol(n); for (int i = 0 ; i < n ; ++i) { sol[i] = answer[dsu.find(i + 1)]; } return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...