Submission #1243313

#TimeUsernameProblemLanguageResultExecution timeMemory
1243313SpyrosAlivSphinx's Riddle (IOI24_sphinx)C++20
1.50 / 100
1 ms412 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<vector<int>> g; const int MN = 251; 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; } 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]); } for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } vector<int> willAsk(n, n); for (int i = 1; i < n; i++) { willAsk[i] = willAsk[i-1] = -1; int tot = perform_experiment(willAsk); if (tot != n) { merge(i - 1, i); } willAsk[i] = willAsk[i-1] = n; } vector<int> ans(n); ans[0] = 0; for (int i = 1; i < n; i++) { if (find(i) == find(i-1)) ans[i] = ans[i-1]; else ans[i] = ans[i-1] + 1; } 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...