Submission #1176706

#TimeUsernameProblemLanguageResultExecution timeMemory
1176706Kanon스핑크스 (IOI24_sphinx)C++20
100 / 100
393 ms1196 KiB
#include <bits/stdc++.h> #include "sphinx.h" using namespace std; class dsu { public: vector<int> p; int n; dsu(int _n) : n(_n) { p.resize(n); iota(p.begin(), p.end(), 0); } inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); } inline bool unite(int x, int y) { x = get(x); y = get(y); if (x != y) { p[x] = y; return true; } return false; } }; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng) // random shuffle : shuffle(.begin(), .end(), rng) const int MAGIC_DEG = 32; vector<int> find_colours(int n, vector<int> X, vector<int> Y) { vector<vector<int>> g(n); for (int i = 0; i < int(X.size()); i++) { int u = X[i], v = Y[i]; g[u].push_back(v); g[v].push_back(u); } vector<int> color(n, -1); vector<vector<int>> monochrome_graph(n); function<void(int, int)> add_color = [&](int v, int col) { if (color[v] != -1) { assert(color[v] == col); return; } color[v] = col; for (int u : monochrome_graph[v]) { add_color(u, col); } }; auto add_monochrome = [&](int u, int v) { if (find(monochrome_graph[u].begin(), monochrome_graph[u].end(), v) != monochrome_graph[u].end()) return; monochrome_graph[u].push_back(v); monochrome_graph[v].push_back(u); }; auto components_of_colored = [&](vector<int> coloring) { dsu d(n); int cnt = n; for (int v = 0; v < n; v++) { if (coloring[v] == -1) { cnt--; continue; } for (int u : g[v]) { if (coloring[u] != coloring[v]) continue; cnt -= d.unite(u, v); } } return cnt; }; for (int v = 0; v < n; v++) { if (int(g[v].size()) > MAGIC_DEG) { vector<int> adj_nodes = g[v]; vector<int> que_colors(n); iota(que_colors.begin(), que_colors.end(), 0); shuffle(que_colors.begin(), que_colors.end(), rng); while (que_colors.size() > adj_nodes.size()) { vector<int> try_color = vector<int>(que_colors.begin(), que_colors.begin() + adj_nodes.size()); que_colors.erase(que_colors.begin(), que_colors.begin() + adj_nodes.size()); vector<int> coloring(n, n); coloring[v] = -1; for (int i = 0; i < int(adj_nodes.size()); i++) { coloring[adj_nodes[i]] = try_color[i]; } int comp_with_unique_v = components_of_colored(coloring) + 1; int comp_with_monochromable_v = perform_experiment(coloring); assert(comp_with_unique_v >= comp_with_monochromable_v); bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v; if (monochrome_reduce_comp) que_colors = try_color; } while (que_colors.size() > 1) { int sz = que_colors.size(); vector<int> Left_colors = vector<int>(que_colors.begin(), que_colors.begin() + sz / 2); vector<int> coloring(n, n); coloring[v] = -1; for (int i = 0; i < int(Left_colors.size()); i++) { coloring[adj_nodes[i]] = Left_colors[i]; } int comp_with_unique_v = components_of_colored(coloring) + 1; int comp_with_monochromable_v = perform_experiment(coloring); assert(comp_with_unique_v >= comp_with_monochromable_v); bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v; if (monochrome_reduce_comp) { que_colors = Left_colors; } else { que_colors = vector<int>(que_colors.begin() + sz / 2, que_colors.end()); } } assert(que_colors.size() == 1); add_color(v, que_colors[0]); } } vector<int> process_order(n); iota(process_order.begin(), process_order.end(), 0); sort(process_order.begin(), process_order.end(), [&](int i, int j){return color[i] > color[j];}); vector<bool> processed(n); dsu forest_spanning_monochrome(n); vector<int> current_roots; for (int v : process_order) { if (color[v] != -1) { vector<int> same_color_adj; for (int u : g[v]) { if (!processed[u]) continue; if (color[u] == color[v]) { same_color_adj.push_back(u); } } for (int u : same_color_adj) { int ru = forest_spanning_monochrome.get(u); auto it = find(current_roots.begin(), current_roots.end(), ru); if (it == current_roots.end()) continue; forest_spanning_monochrome.unite(ru, v); current_roots.erase(it); add_monochrome(u, v); } current_roots.push_back(v); } else { vector<int> adj_nodes_unique_color_root; for (int u : g[v]) { if (!processed[u]) continue; bool Unique = true; for (int w : g[v]) { if (w == u) break; if (!processed[w]) continue; if (forest_spanning_monochrome.get(w) == forest_spanning_monochrome.get(u)) { Unique = false; break; } } if (Unique) adj_nodes_unique_color_root.push_back(u); } vector<int> same_color_adj_nodes; function<void(vector<int>, int)> dfs = [&](vector<int> possible_same_color_adj_nodes, int total_same_color) { if (total_same_color == 0) return; int sz = possible_same_color_adj_nodes.size(); if (total_same_color == sz) { for (int nd : possible_same_color_adj_nodes) same_color_adj_nodes.push_back(nd); return; } vector<int> coloring(n, n); coloring[v] = -1; for (int i = 0; i < sz / 2; i++) { coloring[possible_same_color_adj_nodes[i]] = -1; } int Left_connected_nodes = components_of_colored(coloring) + sz / 2 + 1 - perform_experiment(coloring); int Right_connected_nodes = total_same_color - Left_connected_nodes; dfs(vector<int>(possible_same_color_adj_nodes.begin(), possible_same_color_adj_nodes.begin() + sz / 2), Left_connected_nodes); dfs(vector<int>(possible_same_color_adj_nodes.begin() + sz / 2, possible_same_color_adj_nodes.end()), Right_connected_nodes); }; vector<int> coloring(n, n); coloring[v] = -1; for (int i : adj_nodes_unique_color_root) coloring[i] = -1; int total_same_color = components_of_colored(coloring) + adj_nodes_unique_color_root.size() + 1 - perform_experiment(coloring); dfs(adj_nodes_unique_color_root, total_same_color); for (int nd : same_color_adj_nodes) { add_monochrome(nd, v); nd = forest_spanning_monochrome.get(nd); auto it = find(current_roots.begin(), current_roots.end(), nd); if (it == current_roots.end()) continue; current_roots.erase(it); forest_spanning_monochrome.unite(nd, v); } for (int nd : same_color_adj_nodes) { if (color[nd] != -1) { assert(color[v] == -1 || color[v] == color[nd]); add_color(v, color[nd]); } } current_roots.push_back(v); } processed[v] = true; } vector<int> choose(n); while (true) { bool change = false; for (int v = 0; v < n; v++) { int bal = 0; for (int u : g[v]) { if (choose[u] == (choose[v] ^ 1)) { bal += 1; } else { bal -= 1; } } if (bal < 0) { choose[v] ^= 1; change = true; } } if (!change) break; } vector<vector<int>> Total_adj_batch(2); for (int v = 0; v < n; v++) Total_adj_batch[choose[v]].push_back(v); for (int rot = 0; rot < 2; rot++) { vector<int> Seekers; vector<int> Helpers = Total_adj_batch[rot ^ 1]; for (int v : Total_adj_batch[rot]) { if (color[v] == -1 && forest_spanning_monochrome.get(v) == v) Seekers.push_back(v); } if (Seekers.empty()) continue; for (int col = 0; col < n; col++) { if (Seekers.empty()) break; vector<int> colled; function<void(vector<int>, int, int)> dfs = [&](vector<int> Candidates, int col_spanning_edges, int so_far) { if (col_spanning_edges == 0) return; if (Candidates.size() == 1) { assert(so_far <= 7); colled.push_back(Candidates[0]); return; } int sz = Candidates.size(); vector<int> coloring(n, n); for (int v : Helpers) coloring[v] = col; for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = -1; int Left_col_spanning_edges = components_of_colored(coloring) + sz / 2 - perform_experiment(coloring); bool is_right_needed = col_spanning_edges > Left_col_spanning_edges; int Right_col_spanning_edges = 0; if (is_right_needed) { if (Left_col_spanning_edges > 0) { for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = n; for (int i = sz / 2; i < sz; i++) coloring[Candidates[i]] = -1; Right_col_spanning_edges = components_of_colored(coloring) + sz - sz / 2 - perform_experiment(coloring); assert(Right_col_spanning_edges > 0); } else { Right_col_spanning_edges = col_spanning_edges; } } assert(Left_col_spanning_edges > 0 || Right_col_spanning_edges > 0); dfs(vector<int>(Candidates.begin(), Candidates.begin() + sz / 2), Left_col_spanning_edges, so_far + 1); dfs(vector<int>(Candidates.begin() + sz / 2, Candidates.end()), Right_col_spanning_edges, so_far + 1); }; vector<int> coloring(n, n); for (int v : Seekers) coloring[v] = -1; for (int v : Helpers) coloring[v] = col; int col_spanning_edges = components_of_colored(coloring) + Seekers.size() - perform_experiment(coloring); dfs(Seekers, col_spanning_edges, 0); for (int v : colled) { add_color(v, col); Seekers.erase(find(Seekers.begin(), Seekers.end(), v)); } } assert(Seekers.empty()); } assert(count(color.begin(), color.end(), -1) == 0); return color; }
#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...