oj.uz

Submission #1106630

# Submission time Handle Problem Language Result Execution time Memory
1106630 2024-10-30T18:00:29 Z Octagons Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 961 ms 2452 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#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) {
					for (auto &jj : nds[j]) {
						ee[jj] = 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) {
					for (auto &jj : nds[j]) {
						e[jj] = 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 (auto &jj : nds[cnd[id]]) {
				ret[jj] = 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) {
		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);
	fo.clear();
	so.clear();
	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:237:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     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
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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 10
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 Correct 2 ms 336 KB #experiments: 103
8 Correct 2 ms 484 KB #experiments: 145
9 Correct 2 ms 336 KB #experiments: 138
10 Correct 2 ms 336 KB #experiments: 151
11 Correct 3 ms 336 KB #experiments: 184
12 Correct 4 ms 336 KB #experiments: 349
13 Correct 4 ms 500 KB #experiments: 354
14 Correct 2 ms 336 KB #experiments: 64
15 Correct 6 ms 336 KB #experiments: 269
16 Correct 7 ms 592 KB #experiments: 307
17 Correct 9 ms 336 KB #experiments: 353
18 Correct 9 ms 336 KB #experiments: 389
19 Correct 13 ms 336 KB #experiments: 393
20 Correct 13 ms 532 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 5 ms 336 KB #experiments: 294
25 Correct 6 ms 336 KB #experiments: 344
26 Correct 3 ms 492 KB #experiments: 242
27 Correct 3 ms 336 KB #experiments: 301
28 Correct 6 ms 336 KB #experiments: 343
29 Correct 4 ms 512 KB #experiments: 288
30 Correct 6 ms 336 KB #experiments: 385
31 Correct 8 ms 524 KB #experiments: 345
32 Correct 12 ms 508 KB #experiments: 401
33 Correct 2 ms 336 KB #experiments: 78
34 Correct 9 ms 516 KB #experiments: 397

Subtask #3
33.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 Correct 2 ms 336 KB #experiments: 103
7 Correct 2 ms 484 KB #experiments: 145
8 Correct 2 ms 336 KB #experiments: 138
9 Correct 2 ms 336 KB #experiments: 151
10 Correct 3 ms 336 KB #experiments: 184
11 Correct 4 ms 336 KB #experiments: 349
12 Correct 4 ms 500 KB #experiments: 354
13 Correct 9 ms 336 KB #experiments: 368
14 Correct 17 ms 536 KB #experiments: 708
15 Correct 21 ms 848 KB #experiments: 698
16 Correct 18 ms 592 KB #experiments: 721
17 Correct 22 ms 336 KB #experiments: 908
18 Correct 28 ms 336 KB #experiments: 1270
19 Correct 40 ms 532 KB #experiments: 1961
20 Correct 9 ms 336 KB #experiments: 383
21 Correct 62 ms 524 KB #experiments: 2388

Subtask #4
21.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 336 KB #experiments: 64
6 Correct 6 ms 336 KB #experiments: 269
7 Correct 7 ms 592 KB #experiments: 307
8 Correct 9 ms 336 KB #experiments: 353
9 Correct 9 ms 336 KB #experiments: 389
10 Correct 13 ms 336 KB #experiments: 393
11 Correct 13 ms 532 KB #experiments: 410
12 Correct 8 ms 336 KB #experiments: 409
13 Correct 324 ms 1692 KB #experiments: 980
14 Correct 495 ms 2452 KB #experiments: 1691
15 Correct 586 ms 2192 KB #experiments: 2013
16 Correct 653 ms 2136 KB #experiments: 2308
17 Correct 712 ms 2376 KB #experiments: 2568
18 Correct 708 ms 2120 KB #experiments: 2594
19 Correct 698 ms 2120 KB #experiments: 2642
20 Correct 118 ms 1416 KB #experiments: 309
21 Correct 592 ms 2024 KB #experiments: 2635

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 10
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 Correct 2 ms 336 KB #experiments: 103
8 Correct 2 ms 484 KB #experiments: 145
9 Correct 2 ms 336 KB #experiments: 138
10 Correct 2 ms 336 KB #experiments: 151
11 Correct 3 ms 336 KB #experiments: 184
12 Correct 4 ms 336 KB #experiments: 349
13 Correct 4 ms 500 KB #experiments: 354
14 Correct 2 ms 336 KB #experiments: 64
15 Correct 6 ms 336 KB #experiments: 269
16 Correct 7 ms 592 KB #experiments: 307
17 Correct 9 ms 336 KB #experiments: 353
18 Correct 9 ms 336 KB #experiments: 389
19 Correct 13 ms 336 KB #experiments: 393
20 Correct 13 ms 532 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 5 ms 336 KB #experiments: 294
25 Correct 6 ms 336 KB #experiments: 344
26 Correct 3 ms 492 KB #experiments: 242
27 Correct 3 ms 336 KB #experiments: 301
28 Correct 6 ms 336 KB #experiments: 343
29 Correct 4 ms 512 KB #experiments: 288
30 Correct 6 ms 336 KB #experiments: 385
31 Correct 8 ms 524 KB #experiments: 345
32 Correct 12 ms 508 KB #experiments: 401
33 Correct 2 ms 336 KB #experiments: 78
34 Correct 9 ms 516 KB #experiments: 397
35 Correct 9 ms 336 KB #experiments: 368
36 Correct 17 ms 536 KB #experiments: 708
37 Correct 21 ms 848 KB #experiments: 698
38 Correct 18 ms 592 KB #experiments: 721
39 Correct 22 ms 336 KB #experiments: 908
40 Correct 28 ms 336 KB #experiments: 1270
41 Correct 40 ms 532 KB #experiments: 1961
42 Correct 9 ms 336 KB #experiments: 383
43 Correct 62 ms 524 KB #experiments: 2388
44 Correct 324 ms 1692 KB #experiments: 980
45 Correct 495 ms 2452 KB #experiments: 1691
46 Correct 586 ms 2192 KB #experiments: 2013
47 Correct 653 ms 2136 KB #experiments: 2308
48 Correct 712 ms 2376 KB #experiments: 2568
49 Correct 708 ms 2120 KB #experiments: 2594
50 Correct 698 ms 2120 KB #experiments: 2642
51 Correct 118 ms 1416 KB #experiments: 309
52 Correct 592 ms 2024 KB #experiments: 2635
53 Correct 78 ms 592 KB #experiments: 1957
54 Correct 91 ms 620 KB #experiments: 1931
55 Correct 128 ms 608 KB #experiments: 1966
56 Correct 124 ms 632 KB #experiments: 1892
57 Correct 369 ms 1164 KB #experiments: 1905
58 Correct 361 ms 1128 KB #experiments: 2066
59 Correct 342 ms 1164 KB #experiments: 1917
60 Correct 449 ms 1220 KB #experiments: 2348
61 Correct 41 ms 504 KB #experiments: 1866
62 Correct 45 ms 496 KB #experiments: 2130
63 Correct 51 ms 336 KB #experiments: 2329
64 Correct 102 ms 1116 KB #experiments: 1784
65 Correct 96 ms 616 KB #experiments: 1770
66 Correct 112 ms 612 KB #experiments: 1939
67 Correct 118 ms 764 KB #experiments: 1987
68 Correct 124 ms 984 KB #experiments: 1889
69 Correct 122 ms 908 KB #experiments: 1935
70 Correct 117 ms 592 KB #experiments: 1994
71 Correct 116 ms 628 KB #experiments: 1806
72 Correct 75 ms 816 KB #experiments: 2038
73 Correct 77 ms 588 KB #experiments: 1870
74 Correct 98 ms 840 KB #experiments: 2018
75 Correct 97 ms 616 KB #experiments: 1748
76 Correct 119 ms 636 KB #experiments: 1941
77 Correct 114 ms 624 KB #experiments: 1801
78 Correct 130 ms 592 KB #experiments: 1908
79 Correct 152 ms 908 KB #experiments: 1763
80 Correct 135 ms 660 KB #experiments: 1902
81 Correct 160 ms 940 KB #experiments: 1961
82 Correct 197 ms 692 KB #experiments: 2513
83 Correct 628 ms 1608 KB #experiments: 2146
84 Correct 961 ms 1932 KB #experiments: 2607
85 Correct 47 ms 848 KB #experiments: 466
86 Correct 370 ms 1860 KB #experiments: 2645