Submission #1106574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106574		Octagons	Sphinx's Riddle (IOI24_sphinx)	C++17	32 / 100	727 ms	2124 KiB

sphinx

#include <bits/stdc++.h>
using namespace std;
#include "sphinx.h"
#define sz(x) int(x.size())
int n;
int p[250], sz[250], p2[250], sz2[250], idxo = 1;
vector<int> adj57[250], tr[250], bck[250];
int vis[250];

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;
		}
		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) {
	for (auto &v : tr[u]) {
		if (chk2(u, v)) {
			merge(u, v);
		}
	}
	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:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 0 / 36