oj.uz

Submission #806902

# Submission time Handle Problem Language Result Execution time Memory
806902 2023-08-04T10:57:36 Z gromperen ICC (CEOI16_icc) C++14
0 / 100
 2 ms 468 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());
		vector<int>a,b;
		for (int bit = 0; bit <= 7; ++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;

		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[mid];
				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())) {
				res1 = v[mid];
				r = mid;
			} else {
				l = mid+1;
			}
		}

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

	}
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -