Submission #1210067

#TimeUsernameProblemLanguageResultExecution timeMemory
1210067trimkus스핑크스 (IOI24_sphinx)C++20
28.50 / 100
1283 ms2162688 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; vector<int> E; int N; const int MAXN = 250; int p[MAXN]; bool vis[MAXN]; vector<int> adj[MAXN]; int get(int x) { return (p[x] < 0 ? x : p[x] = get(p[x])); } int color(int x) { return (E[x] >= 0 ? E[x] + N : get(x)); } int expected() { int cnt = 0; auto dfs = [&](auto& dfs, int i) -> void { vis[i] = true; for (auto& u : adj[i]) { if (vis[u]) continue; if (color(i) != color(u)) continue; dfs(dfs, u); } }; for (int i = 0; i < N; ++i) vis[i] = false; for (int i = 0; i < N; ++i) { if (!vis[i]) { cnt++; dfs(dfs, i); } } return cnt; } std::vector<int> find_colours(int _N, std::vector<int> X, std::vector<int> Y) { N = _N; E = vector<int>(N); vector<int> F(N, -1); vector<bool> online(N); for (int i = 0; i < (int)X.size(); ++i) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } for (int i = 0; i < N; ++i) { p[i] = -1; } for (int i = 1; i < N; ++i) { while (true) { for (int j = 0; j <= i; ++j) E[j] = -1; for (int j = i + 1; j < N; ++j) E[j] = N; if (expected() == perform_experiment(E)) { break; } // cerr << "NOW CHECKING: [0, " << i - 1 << "], with vertice at: " << i << endl; // must be at least one vertice same color as i set<int> st; vector<int> pool; for (int j = 0; j < i; ++j) { if (get(j) != i) { st.insert(j); } } while (st.size()) { pool.push_back(*begin(st)); st.erase(begin(st)); } // cerr << "POOL = "; // for (auto& u : pool) { // cerr << u << " "; // } // cerr << "\n"; int left = 0, right = (int)pool.size() - 1; while (left < right) { // cerr << "[" << left << ", " << right << "]\n"; int mid = (left + right) / 2; for (int j = 0; j < N; ++j) { online[j] = false; } for (int j = 0; j <= mid; ++j) { online[pool[j]] = 1; } for (int j = 0; j < i; ++j) { if (online[get(j)]) { E[j] = -1; } else { E[j] = N; } } E[i] = -1; // repetitive? for (int j = i + 1; j < N; ++j) { E[j] = N; } if (expected() == perform_experiment(E)) { left = mid + 1; } else { right = mid; } } p[get(right)] = i; } } map<int, int> mp; for (int i = 0; i < N; ++i) { if (!mp.count(get(i))) { mp[get(i)] = mp.size(); } } for (int i = 0; i < N; ++i) { F[i] = mp[get(i)]; } return F; }
#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...