제출 #1195334

#제출 시각아이디문제언어결과실행 시간메모리
1195334aykhnSphinx's Riddle (IOI24_sphinx)C++20
100 / 100
290 ms1608 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; const int MXN = 250; struct DSU { vector<int> e; void init(int n) { e.assign(n, -1); } int get(int x) { if (e[x] < 0) return x; return e[x] = get(e[x]); } void unite(int x, int y) { x = get(x), y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; int n; vector<int> adj[MXN], g[MXN]; int bic[MXN], u[MXN]; void bicol(int a) { u[a] = 1; for (int &v : g[a]) { if (u[v]) continue; bic[v] = bic[a] ^ 1; bicol(v); } } void dfs(int a, vector<int> &used, vector<int> &col) { used[a] = 1; for (int &v : adj[a]) { if (used[v] || col[v] == -1) continue; dfs(v, used, col); } } int cntNs(vector<int> &col) { int res = 0; vector<int> used(n, 0); for (int i = 0; i < n; i++) { if (!used[i] && col[i] != -1) res++, dfs(i, used, col); } return res; } int getcomps(vector<int> &col) { return perform_experiment(col) - cntNs(col); } vector<int> find_colours(int N, vector<int> X, vector<int> Y) { n = N; for (int i = 0; i < X.size(); i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]); DSU dsu; dsu.init(n); vector<vector<int>> cc; for (int i = 0; i < n; i++) { vector<int> q(n, 0); for (int j = 0; j <= i; j++) q[j] = -1; for (int j = i + 1; j < n; j++) q[j] = n; int cur = getcomps(q); cc.push_back({i}); if (!i || cur == cc.size()) continue; vector<int> del(cc.size(), 0); int cnt = (int)cc.size() - cur; for (int k = 1, l = 0; k <= cnt; k++) { int r = (int)cc.size() - 2; while (l < r) { int mid = (l + r) >> 1; vector<int> q(n, n); for (int i = l; i <= mid; i++) { for (int &j : cc[i]) q[j] = -1; } q[i] = -1; if (getcomps(q) <= mid - l + 1) r = mid; else l = mid + 1; } for (int &j : cc[l]) cc.back().push_back(j); del[l] = 1; l++; } for (int i = (int)cc.size() - 1; i >= 0; i--) if (del[i]) cc.erase(cc.begin() + i); } vector<int> comp(n, 0); for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) comp[j] = i; for (int i = 0; i < X.size(); i++) { if (comp[X[i]] != comp[Y[i]]) g[comp[X[i]]].push_back(comp[Y[i]]), g[comp[Y[i]]].push_back(comp[X[i]]); } for (int i = 0; i < cc.size(); i++) { if (!u[i]) bicol(i); } vector<int> real(cc.size()); for (int val = 0; val < n; val++) { for (int p = 0; p < 2; p++) { vector<int> q(n, val); int cnt = 0; for (int i = 0; i < cc.size(); i++) { if (bic[i] == p) q[cc[i][0]] = -1, cnt++; } int cur = perform_experiment(q); int valcomps = cntNs(q); // cur = valcomps + cnt for (int l = 0; cur < valcomps + cnt;) { int r = (int)cc.size() - 1; while (l < r) { int mid = (l + r) >> 1; vector<int> q(n, val); int cnt = 0; for (int i = l; i <= mid; i++) { if (bic[i] == p) q[cc[i][0]] = -1, cnt++; } if (getcomps(q) == cnt) l = mid + 1; else r = mid; } real[l] = val; cnt--; q[cc[l][0]] = val; valcomps = cntNs(q); l++; } } } vector<int> res(n, 0); for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) res[j] = real[i]; return res; }
#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...