Submission #1227337

#TimeUsernameProblemLanguageResultExecution timeMemory
1227337LucaIlieSphinx's Riddle (IOI24_sphinx)C++20
21.50 / 100
112 ms1728 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 250; 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(1010); int findParent(int v) { if (parent[v] != v) parent[v] = findParent(parent[v]); return parent[v]; } void unionn(int u, int v) { // printf("UNESC %d %d\n", u, 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; // printf("dfs %d\n", u); 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) { // printf("AM DECIS %d %d\n", cand[0], color); 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) cand.push_back(v); else 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; for (int v = 1; v < n; v++) { vector<int> cand; set<int> s; for (int u: adj[v]) { if (u < v) { if (s.find(findParent(u)) == s.end()) { s.insert(findParent(u)); cand.push_back(u); } } } // printf("CAND "); // for (int u: cand) // printf("%d ", u); // printf("\n"); 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)); } for (int v = 0; v < n; v++) { if (findParent(v) != v) continue; totalComp++; sort(adjComp[v].begin(), adjComp[v].end()); adjComp[v].resize(unique(adjComp[v].begin(), adjComp[v].end()) - adjComp[v].begin()); } findSpan(0); for (int c = 0; c < n; c++) { 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...