oj.uz

Submission #806931

# Submission time Handle Problem Language Result Execution time Memory
806931 2023-08-04T11:09:37 Z gromperen ICC (CEOI16_icc) C++14
100 / 100
 103 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! 105 queries used.
2 Correct 5 ms 496 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 504 KB Ok! 536 queries used.
2 Correct 29 ms 500 KB Ok! 677 queries used.
3 Correct 29 ms 468 KB Ok! 664 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 468 KB Ok! 1418 queries used.
2 Correct 89 ms 500 KB Ok! 1622 queries used.
3 Correct 85 ms 468 KB Ok! 1592 queries used.
4 Correct 100 ms 492 KB Ok! 1509 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 508 KB Ok! 1544 queries used.
2 Correct 93 ms 492 KB Ok! 1534 queries used.
3 Correct 90 ms 496 KB Ok! 1602 queries used.
4 Correct 85 ms 500 KB Ok! 1522 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 488 KB Ok! 1605 queries used.
2 Correct 92 ms 488 KB Ok! 1610 queries used.
3 Correct 89 ms 512 KB Ok! 1623 queries used.
4 Correct 87 ms 504 KB Ok! 1605 queries used.
5 Correct 81 ms 492 KB Ok! 1483 queries used.
6 Correct 88 ms 488 KB Ok! 1534 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 504 KB Ok! 1613 queries used.
2 Correct 90 ms 504 KB Ok! 1623 queries used.