oj.uz

Submission #1106567

# Submission time Handle Problem Language Result Execution time Memory
1106567 2024-10-30T16:39:06 Z Octagons Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 544 ms 2048 KB 
#include <bits/stdc++.h>
using namespace std;
#include "sphinx.h"
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 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());
	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]);
	}
	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

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     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 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 1 ms 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 3 ms 336 KB Partially correct
15 Partially correct 4 ms 336 KB Partially correct
16 Partially correct 4 ms 336 KB Partially correct
17 Partially correct 5 ms 336 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 336 KB Partially correct
21 Partially correct 6 ms 336 KB Partially correct
22 Partially correct 5 ms 336 KB Partially correct
23 Partially correct 4 ms 336 KB Partially correct
24 Partially correct 4 ms 336 KB Partially correct
25 Partially correct 6 ms 492 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 508 KB Partially correct
29 Incorrect 3 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 336 KB Partially correct
8 Partially correct 1 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 1 ms 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 6 ms 336 KB Partially correct
14 Partially correct 6 ms 592 KB Partially correct
15 Partially correct 6 ms 336 KB Partially correct
16 Partially correct 6 ms 336 KB Partially correct
17 Partially correct 7 ms 520 KB Partially correct
18 Partially correct 10 ms 336 KB Partially correct
19 Partially correct 10 ms 336 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 6 ms 612 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 3 ms 336 KB Partially correct
6 Partially correct 4 ms 336 KB Partially correct
7 Partially correct 4 ms 336 KB Partially correct
8 Partially correct 5 ms 336 KB Partially correct
9 Partially correct 6 ms 336 KB Partially correct
10 Partially correct 6 ms 336 KB Partially correct
11 Partially correct 6 ms 336 KB Partially correct
12 Partially correct 6 ms 336 KB Partially correct
13 Partially correct 172 ms 1484 KB Partially correct
14 Partially correct 279 ms 1608 KB Partially correct
15 Partially correct 355 ms 1608 KB Partially correct
16 Partially correct 436 ms 1948 KB Partially correct
17 Partially correct 513 ms 2048 KB Partially correct
18 Partially correct 505 ms 1664 KB Partially correct
19 Partially correct 544 ms 1528 KB Partially correct
20 Partially correct 86 ms 1416 KB Partially correct
21 Partially correct 506 ms 1492 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 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 1 ms 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 3 ms 336 KB Partially correct
15 Partially correct 4 ms 336 KB Partially correct
16 Partially correct 4 ms 336 KB Partially correct
17 Partially correct 5 ms 336 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 336 KB Partially correct
21 Partially correct 6 ms 336 KB Partially correct
22 Partially correct 5 ms 336 KB Partially correct
23 Partially correct 4 ms 336 KB Partially correct
24 Partially correct 4 ms 336 KB Partially correct
25 Partially correct 6 ms 492 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 508 KB Partially correct
29 Incorrect 3 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 -