oj.uz

Submission #1106591

# Submission time Handle Problem Language Result Execution time Memory
1106591 2024-10-30T17:24:42 Z Octagons Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 605 ms 2064 KB 
#include <bits/stdc++.h>
using namespace std;
#include "sphinx.h"
#define sz(x) int(x.size())
int n, mmo;
int p[255], sz[255], p2[255], sz2[255], dep[255], idxo = 1;
vector<int> adj57[255], tr[255], bck[255], adj2[255], nds[255];
int vis[255];
bool fnd[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;
		}
		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]);
      return;
	} else {
		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]) {
		if (chk2(u, v)) {
			merge(u, v);
		}
		dfs(v);
	}
}

void init2(int u, int pr) {
	vis[u] = 1;
	for (auto &v : adj2[u]) {
		if (vis[v])continue;
		dep[v] = (dep[u] ^ 1);
		init2(v, u);
	}
}

vector<int> nw(vector<int> x, int u) {
	vector<int> ret;
	for (auto &i : x) {
		if (i == u)continue;
		ret.push_back(i);
	}
	return ret;
}

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;
	  adj2[i].clear();
	  adj57[i].clear();
	  fnd[i] = false;
	  nds[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);
    }
	mmo = X.size();
	init(0, 0);
	dfs(0);
	bool ff = true;
    for (int i = 0; i < n; i++) {
      ret[i] = findp(i);
	  ff &= (findp(i) == findp(0));
    }
	return ret;
	if (ff) {
		for (int i = 0; i < n; i++) {
			vector<int> e(n, n);
			e[0] = -1;
			e[adj57[0][0]] = i;
			if (chk(e)) {
				for (int j = 0; j < n; j++) {
					ret[j] = i;
				}
				break;
			}
		}
		return ret;
	}
	for (int i = 0; i < n; i++) {
		nds[findp(i)].push_back(i);
		for (auto &v : adj57[i]) {
			if (findp(i) == findp(v))continue;
			adj2[findp(i)].push_back(findp(v));
			adj2[findp(v)].push_back(findp(i));
		}
		vis[i] = 0;
		dep[i] = 0;
	}
	init2(findp(0), -1);
	vector<int> fo, so;
	for (int i = 0; i < n; i++) {
		if (findp(i) != i)continue;
		if (dep[i])fo.push_back(i);
		else so.push_back(i);
	}
	for (int i = 0; i < n; i++) {
		vector<int> cnd;
		for (auto &j : fo) {
			if (fnd[j])continue;
			cnd.push_back(j);
		}
		while (!cnd.empty()) {
			int id = -1, l = 0, r = sz(cnd) - 1;
			while (l <= r) {
				int m = (l + r) >> 1;
				vector<int> e(n, n);
				for (auto &j : so) {
					e[j] = i;
				}
				for (int j = 0; j <= m; j++) {
					for (auto &jj : nds[cnd[j]]) {
						e[jj] = -1;
					}
				}
				if (chk(e)) {
					id = m;
					r = m-1;
				} else {
					l = m+1;
				}
			}
			if (id == -1)break;
			fnd[cnd[id]] = true;
			for (int j = 0; j < n; j++) {
				if (findp(j) == cnd[id]) {
					ret[j] = i;
				}
			}
			vector<int> xx;
			for (int j = id+1; j < sz(cnd); j++) {
				xx.push_back(cnd[j]);
			}
			cnd = xx;
		}
	}
	swap(fo, so);
	for (int i = 0; i < n; i++) {
		dep[i] ^= 1;
	}
	for (int i = 0; i < n; i++) {
		vector<int> cnd;
		for (auto &j : fo) {
			if (fnd[j])continue;
			cnd.push_back(j);
		}
		while (!cnd.empty()) {
			int id = -1, l = 0, r = sz(cnd) - 1;
			while (l <= r) {
				int m = (l + r) >> 1;
				vector<int> e(n, n);
				for (auto &j : so) {
					e[j] = i;
				}
				for (int j = 0; j <= m; j++) {
					for (auto &jj : nds[cnd[j]]) {
						e[jj] = -1;
					}
				}
				if (chk(e)) {
					id = m;
					r = m-1;
				} else {
					l = m+1;
				}
			}
			if (id == -1)break;
			fnd[cnd[id]] = true;
			for (int j = 0; j < n; j++) {
				if (findp(j) == cnd[id]) {
					ret[j] = i;
				}
			}
			vector<int> xx;
			for (int j = id+1; j < sz(cnd); j++) {
				xx.push_back(cnd[j]);
			}
			cnd = xx;
		}
	}
    return ret;
}

Compilation message

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #1
1.5 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 336 KB Partially correct
8 Partially correct 1 ms 512 KB Partially correct
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 2 ms 336 KB Partially correct
13 Partially correct 1 ms 504 KB Partially correct
14 Partially correct 2 ms 336 KB Partially correct
15 Partially correct 5 ms 336 KB Partially correct
16 Partially correct 5 ms 336 KB Partially correct
17 Partially correct 6 ms 336 KB Partially correct
18 Partially correct 8 ms 528 KB Partially correct
19 Partially correct 7 ms 520 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 9 ms 528 KB Partially correct
22 Partially correct 4 ms 500 KB Partially correct
23 Partially correct 6 ms 336 KB Partially correct
24 Partially correct 5 ms 336 KB Partially correct
25 Partially correct 4 ms 500 KB Partially correct
26 Partially correct 1 ms 336 KB Partially correct
27 Partially correct 1 ms 336 KB Partially correct
28 Partially correct 1 ms 336 KB Partially correct
29 Incorrect 2 ms 336 KB Vertices 9 and 27 do have the same color, but they do not in returned answer
30 Halted 0 ms 0 KB -

Subtask #3
16.5 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 512 KB Partially correct
8 Partially correct 2 ms 336 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 2 ms 336 KB Partially correct
12 Partially correct 1 ms 504 KB Partially correct
13 Partially correct 6 ms 336 KB Partially correct
14 Partially correct 6 ms 520 KB Partially correct
15 Partially correct 6 ms 336 KB Partially correct
16 Partially correct 8 ms 336 KB Partially correct
17 Partially correct 9 ms 532 KB Partially correct
18 Partially correct 6 ms 336 KB Partially correct
19 Partially correct 6 ms 336 KB Partially correct
20 Partially correct 6 ms 592 KB Partially correct
21 Partially correct 7 ms 592 KB Partially correct

Subtask #4
10.5 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 2 ms 336 KB Partially correct
6 Partially correct 5 ms 336 KB Partially correct
7 Partially correct 5 ms 336 KB Partially correct
8 Partially correct 6 ms 336 KB Partially correct
9 Partially correct 8 ms 528 KB Partially correct
10 Partially correct 7 ms 520 KB Partially correct
11 Partially correct 6 ms 336 KB Partially correct
12 Partially correct 9 ms 528 KB Partially correct
13 Partially correct 200 ms 1524 KB Partially correct
14 Partially correct 313 ms 1440 KB Partially correct
15 Partially correct 443 ms 1464 KB Partially correct
16 Partially correct 471 ms 1552 KB Partially correct
17 Partially correct 550 ms 1528 KB Partially correct
18 Partially correct 594 ms 1928 KB Partially correct
19 Partially correct 605 ms 2064 KB Partially correct
20 Partially correct 97 ms 1420 KB Partially correct
21 Partially correct 564 ms 1676 KB Partially correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 336 KB Partially correct
8 Partially correct 1 ms 512 KB Partially correct
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 2 ms 336 KB Partially correct
13 Partially correct 1 ms 504 KB Partially correct
14 Partially correct 2 ms 336 KB Partially correct
15 Partially correct 5 ms 336 KB Partially correct
16 Partially correct 5 ms 336 KB Partially correct
17 Partially correct 6 ms 336 KB Partially correct
18 Partially correct 8 ms 528 KB Partially correct
19 Partially correct 7 ms 520 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 9 ms 528 KB Partially correct
22 Partially correct 4 ms 500 KB Partially correct
23 Partially correct 6 ms 336 KB Partially correct
24 Partially correct 5 ms 336 KB Partially correct
25 Partially correct 4 ms 500 KB Partially correct
26 Partially correct 1 ms 336 KB Partially correct
27 Partially correct 1 ms 336 KB Partially correct
28 Partially correct 1 ms 336 KB Partially correct
29 Incorrect 2 ms 336 KB Vertices 9 and 27 do have the same color, but they do not in returned answer
30 Halted 0 ms 0 KB -