Submission #1106579

#TimeUsernameProblemLanguageResultExecution timeMemory
1106579OctagonsSphinx's Riddle (IOI24_sphinx)C++17
32 / 100
739 ms1948 KiB
#include <bits/stdc++.h> using namespace std; #include "sphinx.h" #define sz(x) int(x.size()) int n; int p[255], sz[255], p2[255], sz2[255], idxo = 1; vector<int> adj57[255], tr[255], bck[255]; int vis[255]; int findp2(int u) { return p2[u] = (p2[u] == u ? u : findp2(p2[u])); } bool merge2(int u, int v) { u = findp2(u), v = findp2(v); if (u == v)return false; if (sz2[u] < sz2[v])swap(u, v); sz2[u] += sz2[v]; p2[v] = u; return true; } int findp(int u) { return p[u] = (p[u] == u ? u : findp(p[u])); } void merge(int u, int v) { u = findp(u), v = findp(v); if (u == v)return; if (sz[u] < sz[v])swap(u, v); sz[u] += sz[v]; p[v] = u; } bool chk(vector<int> v) { for (int i = 0; i < n; i++) { p2[i] = i; sz2[i] = 1; } int comps = n; for (int i = 0; i < n; i++) { for (auto &vv : adj57[i]) { if (~v[i] && v[i] == v[vv]) { comps -= merge2(i, vv); } else if (v[i] == -1 && v[vv] == -1 && findp(i) == findp(vv)) { comps -= merge2(i, vv); } } } int x = perform_experiment(v); return (comps > x); } bool chk2(int u, int v) { for (int i = 0; i < n; i++) { p2[i] = i; sz2[i] = 1; } int comps = n; vector<int> e(n, n); e[u] = e[v] = -1; for (int i = 0; i < n; i++) { for (auto &vv : adj57[i]) { if (e[i] == e[vv]) { comps -= merge2(i, vv); } } } int x = perform_experiment(e); return (comps == x); } void init(int u, int pr) { vis[u] = idxo++; for (auto &v : adj57[u]) { if (v == pr)continue; if (vis[v]) { if (vis[v] < vis[u])bck[u].push_back(v); continue; } if (chk2(u, v)) { merge(u, v); } init(v, u); tr[u].push_back(v); } } void soly(int u, vector<int> vvo) { if (vvo.empty())return; int l = 0, r = int(vvo.size()) - 1, id = -1; while (l <= r) { int m = (l + r) >> 1; vector<int> e(n, n); for (int j = 0; j <= m; j++) { for (int i = 0; i < n; i++) { if (findp(i) == vvo[j])e[i] = -1; } } e[u] = -1; if (chk(e)) { id = m; r = m-1; } else { l = m+1; } } if (~id) { merge(u, vvo[id]); } else { return; } if (id == sz(vvo)-1)return; vector<int> xx; for (int i = id+1; i < sz(vvo); i++) { xx.push_back(vvo[i]); } soly(u, xx); } void dfs(int u) { vector<int> vvo; for (auto &v : bck[u]) { if (findp(v) != findp(u))vvo.push_back(findp(v)); } sort(vvo.begin(), vvo.end()); vvo.erase(unique(vvo.begin(), vvo.end()), vvo.end()); soly(u, vvo); for (auto &v : tr[u]) { dfs(v); } } std::vector<int> find_colours(int NH, std::vector<int> X, std::vector<int> Y) { n = NH; vector<int> ret(n, 0); for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; adj57[i].clear(); tr[i].clear(); bck[i].clear(); vis[i] = 0; } for (int i = 0; i < X.size(); i++) { int u = X[i], v = Y[i]; adj57[u].push_back(v); adj57[v].push_back(u); } init(0, 0); dfs(0); for (int i = 0; i < n; i++) { ret[i] = findp(i); } return ret; }

Compilation message (stderr)

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
#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...