Submission #1227457

#TimeUsernameProblemLanguageResultExecution timeMemory
1227457LucaIlieSphinx's Riddle (IOI24_sphinx)C++20
57 / 100
163 ms1732 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 300; int n, m; int vert; int parent[MAX_N]; int depth[MAX_N]; bool vis[MAX_N]; int finalColor[MAX_N]; vector<int> adj[MAX_N]; vector<int> adjComp[MAX_N]; vector<int> comp[MAX_N]; mt19937 rnd(101); int findParent(int v) { if (parent[v] != v) parent[v] = findParent(parent[v]); return parent[v]; } void unionn(int u, int v) { u = findParent(u); v = findParent(v); if (u == v) return; parent[u] = v; } int totalComp; int E[MAX_N]; void dfsComp(int u, int t) { vis[u] = true; vector<int> adjj = (t == 1 ? adjComp[u] : adj[u]); for (int v: adjj) { if (vis[v] || E[u] != E[v]) continue; dfsComp(v, t); } } void findComp(vector<int> e, int t) { for (int v = 0; v < n; v++) { E[v] = e[v]; vis[v] = false; } totalComp = 0; for (int v = 0; v < n; v++) { if (t == 1 && findParent(v) != v) continue; if (vis[v]) continue; totalComp++; if (e[v] == -1) continue; dfsComp(v, t); } for (int v = 0; v < n; v++) { E[v] = 0; vis[v] = false; } } int ask(vector<int> v) { vector<int> e(n, n); for (int i: v) e[i] = -1; e[vert] = -1; int a = perform_experiment(e); for (int i: v) e[i] = 0; e[vert] = 0; findComp(e, 0); // int b = perform_experiment(e); int b = totalComp; return v.size() - a + b; } void divide(vector<int> cand, int c) { shuffle(cand.begin(), cand.end(), rnd); int n = cand.size(); if (n == 0) return; if (c == -1) c = ask(cand); if (c == 0) return; if (n == 1) { unionn(vert, cand[0]); return; } vector<int> a, b; for (int i = 0; i < n / 2; i++) a.push_back(cand[i]); for (int i = n / 2; i < n; i++) b.push_back(cand[i]); int aa = ask(a); int bb = c - aa; if (aa > 0) divide(a, aa); if (bb > 0) divide(b, bb); } void findSpan(int u) { vis[u] = true; for (int v: adjComp[u]) { if (vis[v]) continue; depth[v] = depth[u] + 1; findSpan(v); } } int color; vector<int> fixedC; int ask2(vector<int> v) { vector<int> e(n, n); for (int i: fixedC) { for (int v: comp[i]) e[v] = color; } for (int i: v) { for (int v: comp[i]) e[v] = -1; } int a = perform_experiment(e); findComp(e, 1); return totalComp - a; } void divide2(vector<int> cand, int ans) { shuffle(cand.begin(), cand.end(), rnd); int n = cand.size(); if (n == 0) return; if (ans == -1) ans = ask2(cand); if (ans == 0) return; if (n == 1) { finalColor[cand[0]] = color; return; } vector<int> a, b; for (int i = 0; i < n / 2; i++) a.push_back(cand[i]); for (int i = n / 2; i < n; i++) b.push_back(cand[i]); int aa = ask2(a); int bb = ans - aa; if (aa > 0) divide2(a, aa); if (bb > 0) divide2(b, bb); } void findColors(int c, int p) { vector<int> cand; fixedC.clear(); color = c; for (int v = 0; v < n; v++) { if (findParent(v) != v) continue; if (depth[v] % 2 == p && finalColor[v] == -1) cand.push_back(v); else if (depth[v] % 2 != p) fixedC.push_back(v); } divide2(cand, -1); } vector<int> find_colours(int N, vector<int> X, vector<int> Y) { n = N; m = X.size(); for (int i = 0; i < m; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } for (int v = 0; v < n; v++) parent[v] = v; vector<int> perm(n); for (int i = 0; i < n; i++) perm[i] = i; // shuffle(perm.begin(), perm.end(), rnd); vector<bool> used(n, false); used[perm[0]] = true; for (int i = 1; i < n; i++) { int v = perm[i]; used[v] = true; vector<int> cand; set<int> s; for (int u: adj[v]) { if (used[u]) { if (s.find(findParent(u)) == s.end()) { s.insert(findParent(u)); cand.push_back(u); } } } vert = v; divide(cand, -1); } for (int v = 0; v < n; v++) { comp[findParent(v)].push_back(v); for (int u: adj[v]) adjComp[findParent(v)].push_back(findParent(u)); } totalComp = 0; for (int v = 0; v < n; v++) { if (findParent(v) != v) continue; totalComp++; finalColor[v] = -1; sort(adjComp[v].begin(), adjComp[v].end()); adjComp[v].resize(unique(adjComp[v].begin(), adjComp[v].end()) - adjComp[v].begin()); } if (totalComp == 1) { vector<int> e(n, -1); for (int c = 0; c < n; c++) { e[0] = c; if (perform_experiment(e) == 1) { finalColor[findParent(0)] = c; break; } } } else { findSpan(0); shuffle(perm.begin(), perm.end(), rnd); for (int i = 0; i < n; i++) { int c = perm[i]; findColors(c, 0); findColors(c, 1); } } vector<int> ans(n); for (int v = 0; v < n; v++) ans[v] = finalColor[findParent(v)]; return ans; }
#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...