Submission #1243312

#TimeUsernameProblemLanguageResultExecution timeMemory
1243312SpyrosAlivSphinx's Riddle (IOI24_sphinx)C++20
10 / 100
17 ms1168 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<vector<int>> g; const int MN = 51; int par[MN], sz[MN]; int find(int u) { if (par[u] == u) return u; return par[u] = find(par[u]); } bool merge(int u, int v) { u = find(u); v = find(v); if ( u== v) return false; if (sz[u] > sz[v]) swap(u, v); par[u] = v; sz[v] += sz[u]; return true; } int get_comps(vector<int> cols) { for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } int tot = n; for (int i = 0; i < n; i++) { for (auto nxt: g[i]) { if (cols[i] == cols[nxt]) { tot -= merge(i, nxt);; } } } return tot; } vector<int> find_colours(int N, vector<int> X, vector<int> Y) { n = N; m = Y.size(); g.resize(n); for (int i = 0; i < m; i++) { g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } vector<int> ans(n, -1); for (int i = 0; i < n; i++) { int nxt = g[i][0]; vector<int> willAsk(n, n); willAsk[i] = -1; for (int j = 0; j < n; j++) { willAsk[nxt] = j; int tot = perform_experiment(willAsk); if (tot != get_comps(willAsk)) { ans[i] = j; break; } } } 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...