oj.uz

Submission #1106588

# Submission time Handle Problem Language Result Execution time Memory
1106588 2024-10-30T17:19:45 Z Octagons Sphinx's Riddle (IOI24_sphinx) C++17
6.5 / 100
 788 ms 2200 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]);
	} 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));
    }
	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:166:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 9

Subtask #1
3.0 / 3.0

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

Subtask #2
3.5 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 9
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 4
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 1 ms 336 KB #experiments: 74
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 4 ms 336 KB Partially correct
9 Correct 3 ms 336 KB #experiments: 203
10 Partially correct 3 ms 336 KB Partially correct
11 Partially correct 3 ms 336 KB Partially correct
12 Correct 5 ms 336 KB #experiments: 537
13 Correct 6 ms 336 KB #experiments: 540
14 Correct 2 ms 592 KB #experiments: 64
15 Correct 7 ms 336 KB #experiments: 308
16 Correct 9 ms 336 KB #experiments: 393
17 Correct 16 ms 592 KB #experiments: 482
18 Correct 14 ms 336 KB #experiments: 642
19 Correct 13 ms 780 KB #experiments: 638
20 Correct 14 ms 524 KB #experiments: 743
21 Correct 16 ms 524 KB #experiments: 772
22 Correct 8 ms 336 KB #experiments: 379
23 Correct 6 ms 336 KB #experiments: 372
24 Correct 6 ms 336 KB #experiments: 397
25 Correct 10 ms 336 KB #experiments: 514
26 Partially correct 4 ms 508 KB Partially correct
27 Partially correct 5 ms 336 KB Partially correct
28 Correct 5 ms 336 KB #experiments: 523
29 Partially correct 7 ms 336 KB Partially correct
30 Correct 9 ms 336 KB #experiments: 642
31 Correct 15 ms 336 KB #experiments: 489
32 Correct 14 ms 336 KB #experiments: 692
33 Correct 2 ms 336 KB #experiments: 78
34 Correct 20 ms 336 KB #experiments: 757

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 4
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 1 ms 336 KB #experiments: 74
6 Partially correct 2 ms 336 KB Partially correct
7 Partially correct 4 ms 336 KB Partially correct
8 Correct 3 ms 336 KB #experiments: 203
9 Partially correct 3 ms 336 KB Partially correct
10 Partially correct 3 ms 336 KB Partially correct
11 Correct 5 ms 336 KB #experiments: 537
12 Correct 6 ms 336 KB #experiments: 540
13 Partially correct 20 ms 336 KB Partially correct
14 Partially correct 26 ms 336 KB Partially correct
15 Partially correct 34 ms 592 KB Partially correct
16 Partially correct 32 ms 336 KB Partially correct
17 Partially correct 55 ms 608 KB Partially correct
18 Incorrect 72 ms 532 KB #experiments reached 2751
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 2
2 Correct 1 ms 336 KB #experiments: 4
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 2 ms 592 KB #experiments: 64
6 Correct 7 ms 336 KB #experiments: 308
7 Correct 9 ms 336 KB #experiments: 393
8 Correct 16 ms 592 KB #experiments: 482
9 Correct 14 ms 336 KB #experiments: 642
10 Correct 13 ms 780 KB #experiments: 638
11 Correct 14 ms 524 KB #experiments: 743
12 Correct 16 ms 524 KB #experiments: 772
13 Correct 282 ms 1680 KB #experiments: 926
14 Correct 619 ms 2200 KB #experiments: 2104
15 Incorrect 788 ms 2124 KB #experiments reached 2751
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 9
2 Correct 1 ms 336 KB #experiments: 2
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 4
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 1 ms 336 KB #experiments: 74
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 4 ms 336 KB Partially correct
9 Correct 3 ms 336 KB #experiments: 203
10 Partially correct 3 ms 336 KB Partially correct
11 Partially correct 3 ms 336 KB Partially correct
12 Correct 5 ms 336 KB #experiments: 537
13 Correct 6 ms 336 KB #experiments: 540
14 Correct 2 ms 592 KB #experiments: 64
15 Correct 7 ms 336 KB #experiments: 308
16 Correct 9 ms 336 KB #experiments: 393
17 Correct 16 ms 592 KB #experiments: 482
18 Correct 14 ms 336 KB #experiments: 642
19 Correct 13 ms 780 KB #experiments: 638
20 Correct 14 ms 524 KB #experiments: 743
21 Correct 16 ms 524 KB #experiments: 772
22 Correct 8 ms 336 KB #experiments: 379
23 Correct 6 ms 336 KB #experiments: 372
24 Correct 6 ms 336 KB #experiments: 397
25 Correct 10 ms 336 KB #experiments: 514
26 Partially correct 4 ms 508 KB Partially correct
27 Partially correct 5 ms 336 KB Partially correct
28 Correct 5 ms 336 KB #experiments: 523
29 Partially correct 7 ms 336 KB Partially correct
30 Correct 9 ms 336 KB #experiments: 642
31 Correct 15 ms 336 KB #experiments: 489
32 Correct 14 ms 336 KB #experiments: 692
33 Correct 2 ms 336 KB #experiments: 78
34 Correct 20 ms 336 KB #experiments: 757
35 Partially correct 20 ms 336 KB Partially correct
36 Partially correct 26 ms 336 KB Partially correct
37 Partially correct 34 ms 592 KB Partially correct
38 Partially correct 32 ms 336 KB Partially correct
39 Partially correct 55 ms 608 KB Partially correct
40 Incorrect 72 ms 532 KB #experiments reached 2751
41 Halted 0 ms 0 KB -