oj.uz

Submission #1106608

# Submission time Handle Problem Language Result Execution time Memory
1106608 2024-10-30T17:35:02 Z Octagons Sphinx's Riddle (IOI24_sphinx) C++17
50 / 100
 926 ms 2364 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], ret;
int vis[255];
bool fnd[255];
vector<int> fo, so;

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;
	vector<int> ee(n, n);
	for (int j = 0; j < sz(vvo); j++) {
		for (int i = 0; i < n; i++) {
			if (findp(i) == vvo[j])ee[i] = -1;
		}
	}
	ee[u] = -1;
	if (sz(vvo) > 1) {
		if (!chk(ee))return;
	}
	int l = 0, r = int(vvo.size()) - 1 - (sz(vvo) > 1), id = (sz(vvo) > 1 ? int(vvo.size())-1 : -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> reti;
	for (auto &i : x) {
		if (i == u)continue;
		reti.push_back(i);
	}
	return reti;
}

void doyi() {
	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()) {
			if (sz(cnd) > 1) {
				vector<int> ee(n, n);
				for (auto &j : so) {
					ee[j] = i;
				}
				for (int j = 0; j < sz(cnd); j++) {
					for (auto &jj : nds[cnd[j]]) {
						ee[jj] = -1;
					}
				}
				if (!chk(ee))break;
			}
			int id = (sz(cnd) > 1 ? sz(cnd) - 1 : -1), l = 0, r = sz(cnd) - 1 - (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;
		}
	}
}

std::vector<int> find_colours(int NH, std::vector<int> X, std::vector<int> Y) {
    n = NH;
	fo.clear();
	so.clear();
    ret = vector<int> (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) {
		return ret;
		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);
	for (int i = 0; i < n; i++) {
		if (findp(i) != i)continue;
		if (dep[i])fo.push_back(i);
		else so.push_back(i);
	}
	doyi();
	swap(fo, so);
	for (int i = 0; i < n; i++) {
		dep[i] ^= 1;
	}
	doyi();
    return ret;
}

Compilation message

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:234:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |     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: 10

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: 4
3 Correct 1 ms 336 KB #experiments: 4
4 Partially correct 1 ms 336 KB Partially correct

Subtask #2
3.5 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 10
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 4
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 3 ms 336 KB Partially correct
9 Correct 2 ms 336 KB #experiments: 138
10 Partially correct 2 ms 336 KB Partially correct
11 Partially correct 3 ms 336 KB Partially correct
12 Correct 4 ms 336 KB #experiments: 349
13 Correct 6 ms 336 KB #experiments: 354
14 Partially correct 2 ms 336 KB Partially correct
15 Correct 6 ms 336 KB #experiments: 269
16 Correct 7 ms 336 KB #experiments: 307
17 Correct 11 ms 336 KB #experiments: 353
18 Correct 12 ms 504 KB #experiments: 389
19 Correct 8 ms 336 KB #experiments: 393
20 Correct 8 ms 336 KB #experiments: 410
21 Correct 8 ms 336 KB #experiments: 409
22 Correct 5 ms 336 KB #experiments: 290
23 Correct 5 ms 336 KB #experiments: 285
24 Correct 6 ms 496 KB #experiments: 294
25 Correct 5 ms 336 KB #experiments: 344
26 Partially correct 4 ms 336 KB Partially correct
27 Partially correct 3 ms 336 KB Partially correct
28 Correct 4 ms 336 KB #experiments: 343
29 Partially correct 7 ms 604 KB Partially correct
30 Correct 6 ms 336 KB #experiments: 385
31 Correct 9 ms 772 KB #experiments: 345
32 Correct 9 ms 336 KB #experiments: 401
33 Partially correct 1 ms 336 KB Partially correct
34 Correct 9 ms 592 KB #experiments: 397

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: 4
3 Correct 1 ms 336 KB #experiments: 4
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Partially correct 3 ms 336 KB Partially correct
8 Correct 2 ms 336 KB #experiments: 138
9 Partially correct 2 ms 336 KB Partially correct
10 Partially correct 3 ms 336 KB Partially correct
11 Correct 4 ms 336 KB #experiments: 349
12 Correct 6 ms 336 KB #experiments: 354
13 Partially correct 13 ms 524 KB Partially correct
14 Partially correct 23 ms 336 KB Partially correct
15 Partially correct 16 ms 336 KB Partially correct
16 Partially correct 18 ms 336 KB Partially correct
17 Partially correct 31 ms 520 KB Partially correct
18 Partially correct 31 ms 336 KB Partially correct
19 Correct 45 ms 336 KB #experiments: 1961
20 Partially correct 6 ms 336 KB Partially correct
21 Correct 51 ms 848 KB #experiments: 2388

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: 4
3 Correct 1 ms 336 KB #experiments: 4
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 2 ms 336 KB Partially correct
6 Correct 6 ms 336 KB #experiments: 269
7 Correct 7 ms 336 KB #experiments: 307
8 Correct 11 ms 336 KB #experiments: 353
9 Correct 12 ms 504 KB #experiments: 389
10 Correct 8 ms 336 KB #experiments: 393
11 Correct 8 ms 336 KB #experiments: 410
12 Correct 8 ms 336 KB #experiments: 409
13 Correct 287 ms 2120 KB #experiments: 980
14 Correct 499 ms 2204 KB #experiments: 1691
15 Correct 560 ms 2364 KB #experiments: 2013
16 Correct 617 ms 2268 KB #experiments: 2308
17 Correct 693 ms 2148 KB #experiments: 2568
18 Correct 652 ms 2108 KB #experiments: 2594
19 Correct 660 ms 2052 KB #experiments: 2642
20 Partially correct 86 ms 1416 KB Partially correct
21 Correct 573 ms 2012 KB #experiments: 2635

Subtask #5
18.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 10
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 4
4 Correct 1 ms 336 KB #experiments: 4
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 2 ms 336 KB Partially correct
8 Partially correct 3 ms 336 KB Partially correct
9 Correct 2 ms 336 KB #experiments: 138
10 Partially correct 2 ms 336 KB Partially correct
11 Partially correct 3 ms 336 KB Partially correct
12 Correct 4 ms 336 KB #experiments: 349
13 Correct 6 ms 336 KB #experiments: 354
14 Partially correct 2 ms 336 KB Partially correct
15 Correct 6 ms 336 KB #experiments: 269
16 Correct 7 ms 336 KB #experiments: 307
17 Correct 11 ms 336 KB #experiments: 353
18 Correct 12 ms 504 KB #experiments: 389
19 Correct 8 ms 336 KB #experiments: 393
20 Correct 8 ms 336 KB #experiments: 410
21 Correct 8 ms 336 KB #experiments: 409
22 Correct 5 ms 336 KB #experiments: 290
23 Correct 5 ms 336 KB #experiments: 285
24 Correct 6 ms 496 KB #experiments: 294
25 Correct 5 ms 336 KB #experiments: 344
26 Partially correct 4 ms 336 KB Partially correct
27 Partially correct 3 ms 336 KB Partially correct
28 Correct 4 ms 336 KB #experiments: 343
29 Partially correct 7 ms 604 KB Partially correct
30 Correct 6 ms 336 KB #experiments: 385
31 Correct 9 ms 772 KB #experiments: 345
32 Correct 9 ms 336 KB #experiments: 401
33 Partially correct 1 ms 336 KB Partially correct
34 Correct 9 ms 592 KB #experiments: 397
35 Partially correct 13 ms 524 KB Partially correct
36 Partially correct 23 ms 336 KB Partially correct
37 Partially correct 16 ms 336 KB Partially correct
38 Partially correct 18 ms 336 KB Partially correct
39 Partially correct 31 ms 520 KB Partially correct
40 Partially correct 31 ms 336 KB Partially correct
41 Correct 45 ms 336 KB #experiments: 1961
42 Partially correct 6 ms 336 KB Partially correct
43 Correct 51 ms 848 KB #experiments: 2388
44 Correct 287 ms 2120 KB #experiments: 980
45 Correct 499 ms 2204 KB #experiments: 1691
46 Correct 560 ms 2364 KB #experiments: 2013
47 Correct 617 ms 2268 KB #experiments: 2308
48 Correct 693 ms 2148 KB #experiments: 2568
49 Correct 652 ms 2108 KB #experiments: 2594
50 Correct 660 ms 2052 KB #experiments: 2642
51 Partially correct 86 ms 1416 KB Partially correct
52 Correct 573 ms 2012 KB #experiments: 2635
53 Correct 85 ms 580 KB #experiments: 1957
54 Correct 89 ms 764 KB #experiments: 1931
55 Correct 139 ms 612 KB #experiments: 1966
56 Correct 113 ms 640 KB #experiments: 1892
57 Correct 348 ms 1100 KB #experiments: 1905
58 Correct 354 ms 1408 KB #experiments: 2066
59 Correct 348 ms 1656 KB #experiments: 1917
60 Correct 411 ms 1224 KB #experiments: 2348
61 Partially correct 45 ms 336 KB Partially correct
62 Partially correct 60 ms 592 KB Partially correct
63 Correct 62 ms 336 KB #experiments: 2329
64 Partially correct 119 ms 604 KB Partially correct
65 Partially correct 91 ms 596 KB Partially correct
66 Partially correct 113 ms 624 KB Partially correct
67 Correct 110 ms 616 KB #experiments: 1987
68 Partially correct 131 ms 900 KB Partially correct
69 Correct 122 ms 736 KB #experiments: 1935
70 Correct 153 ms 592 KB #experiments: 1994
71 Partially correct 112 ms 892 KB Partially correct
72 Partially correct 80 ms 808 KB Partially correct
73 Partially correct 97 ms 816 KB Partially correct
74 Correct 130 ms 592 KB #experiments: 2018
75 Partially correct 126 ms 1120 KB Partially correct
76 Correct 114 ms 628 KB #experiments: 1941
77 Partially correct 128 ms 976 KB Partially correct
78 Partially correct 141 ms 848 KB Partially correct
79 Partially correct 131 ms 920 KB Partially correct
80 Partially correct 143 ms 592 KB Partially correct
81 Correct 150 ms 912 KB #experiments: 1961
82 Correct 207 ms 680 KB #experiments: 2513
83 Correct 610 ms 1752 KB #experiments: 2146
84 Correct 926 ms 1932 KB #experiments: 2607
85 Partially correct 22 ms 720 KB Partially correct
86 Correct 364 ms 1096 KB #experiments: 2645