oj.uz

Submission #806930

# Submission time Handle Problem Language Result Execution time Memory
806930 2023-08-04T11:09:05 Z gromperen ICC (CEOI16_icc) C++14
90 / 100
 116 ms 512 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 105;

int who[MAXN];
vector<int> children[MAXN];

int find_set(int x) {
	if (x == who[x]) return x;
	return who[x] = find_set(who[x]);
}

void unite(int x, int y) {
	x = find_set(x);
	y = find_set(y);

	if (x == y) return;
	if (children[x].size() < children[y].size()) swap(x,y);
	who[y] = x;
	for(int i : children[y]) children[x].push_back(i);
	children[y].clear();
}

void run(int n) {
	srand(420);
	for (int i = 1; i <= n; ++i) {
		who[i] = i;
		children[i].push_back(i);
	}

	for(int p = 0; p < n-1; ++p) {
		set<int> s;
		vector<int> components;
		for (int i = 1; i <= n; ++i) s.insert(find_set(i));
		for (int i : s) components.push_back(i);
		random_shuffle(components.begin(), components.end());
		//sort(components.begin(), components.end(), [] (int a, int b) {
				//return children[a].size() > children[b].size();
				//});
		vector<int>a,b;
		for (int bit = 0; bit < 8; ++bit) {
			vector<int> v1, v2;
			for (int i = 0; i < components.size(); ++i) {
				if (i & (1<<bit)) for (int j : children[components[i]]) v1.push_back(j);
				else for (int j : children[components[i]]) v2.push_back(j);
			}

			if (query(v1.size(), v2.size(), v1.data(), v2.data())) {
				a = v1;
				b = v2;
				break;
			}
		}
		int l = 0, r = a.size();
		int res1 = -1;
		//sort(a.begin(), a.end());
		//sort(b.begin(), b.end());
		//reverse(a.begin(), a.end());
		//reverse(b.begin(), b.end());

		//random_shuffle(a.begin(), a.end());
		while (l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for (int i = 0; i <= mid; ++i) v.push_back(a[i]);
			if (query(v.size(), b.size(), v.data(), b.data())) {
				res1 = v.back();
				r = mid;
			} else {
				l = mid+1;
			}
		}
		l = 0, r = b.size();
		int res2 = -1;

		//random_shuffle(b.begin(), b.end());
		while (l < r) {
			int mid = (l+r)/2;
			vector<int> v;
			for (int i = 0; i <= mid; ++i) v.push_back(b[i]);
			if (query(v.size(), a.size(), v.data(), a.data())) {
				res2 = v.back();
				r = mid;
			} else {
				l = mid+1;
			}
		}

		unite(res1, res2);
		setRoad(res1, res2);

	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for (int i = 0; i < components.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Ok! 109 queries used.
2 Correct 4 ms 468 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 504 KB Ok! 534 queries used.
2 Correct 28 ms 500 KB Ok! 679 queries used.
3 Correct 27 ms 496 KB Ok! 660 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 500 KB Ok! 1432 queries used.
2 Correct 98 ms 504 KB Ok! 1671 queries used.
3 Correct 85 ms 504 KB Ok! 1630 queries used.
4 Correct 89 ms 492 KB Ok! 1502 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 492 KB Ok! 1515 queries used.
2 Correct 88 ms 488 KB Ok! 1522 queries used.
3 Correct 95 ms 504 KB Ok! 1626 queries used.
4 Correct 79 ms 492 KB Ok! 1484 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 504 KB Ok! 1609 queries used.
2 Correct 88 ms 504 KB Ok! 1632 queries used.
3 Correct 116 ms 468 KB Ok! 1636 queries used.
4 Correct 85 ms 504 KB Ok! 1612 queries used.
5 Correct 85 ms 488 KB Ok! 1459 queries used.
6 Correct 88 ms 468 KB Ok! 1558 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 512 KB Ok! 1622 queries used.
2 Incorrect 93 ms 496 KB Too many queries! 1660 out of 1625
3 Halted 0 ms 0 KB -