oj.uz

Submission #1117006

# Submission time Handle Problem Language Result Execution time Memory
1117006 2024-11-22T18:20:15 Z ThegeekKnight16 ICC (CEOI16_icc) C++17
100 / 100
 86 ms 764 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> pai, sub;
vector<vector<int>> nodes;

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int a, int b)
{
	a = find(a); b = find(b);
	if (a == b) return;
	if (sub[a] < sub[b]) swap(a, b);
	pai[b] = a; sub[a] += sub[b];
	for (auto x : nodes[b]) nodes[a].push_back(x);
	nodes[b].clear(); sub[b] = 0;
}

int askQuery(const vector<int> &a, const vector<int> &b)
{
	// cerr << "query (pre): " << '\n';
	// cerr << "a: "; for (auto x : a) cerr << x << " "; cerr << '\n';
	// cerr << "b: "; for (auto x : b) cerr << x << " "; cerr << '\n';
	int sz_a = 0, sz_b = 0;
	for (auto x : a) sz_a += sub[x];
	for (auto x : b) sz_b += sub[x];
	// cerr << "sz_a: " << sz_a << ", sz_b: " << sz_b << '\n';
	if (sz_a == 0 || sz_b == 0) return 0;
	int A[sz_a], B[sz_b];
	int idA = 0, idB = 0;
	for (auto x : a) for (auto v : nodes[x]) A[idA++] = v;
	for (auto x : b) for (auto v : nodes[x]) B[idB++] = v;
	// cerr << "query: " << '\n';
	// cerr << "A: "; for (int i = 0; i < sz_a; i++) cerr << A[i] << " "; cerr << '\n';
	// cerr << "B: "; for (int i = 0; i < sz_b; i++) cerr << B[i] << " "; cerr << '\n';
	return query(sz_a, sz_b, A, B);
}

pair<int, int> findComps(const vector<int> &v)
{
	int N = v.size(), K = 31 - __builtin_clz(N-1);

	int diff = 0;
	for (int k = K; k >= 0; k--)
	{
		vector<int> a, b;
		for (int i = 0; i < N; i++) 
		{
			if (i&(1 << k)) a.push_back(v[i]);
			else b.push_back(v[i]);
		}
		diff |= ((askQuery(a, b)) << k);
	}
	// cerr << "diff: " << diff << '\n';

	int id = 31 - __builtin_clz(diff);
	vector<int> a, b;
	for (int i = 0; i < N; i++) 
	{
		if (i&(1 << id)) a.push_back(v[i]);
		else b.push_back(i);
	}
	int ini = 0, fim = b.size()-1;
	while (ini < fim)
	{
		int m = (ini + fim) >> 1;
		vector<int> aux; aux.reserve(m-ini+1);
		for (int i = ini; i <= m; i++) aux.push_back(v[b[i]]);
		// cerr << "ini: " << ini << ", m: " << m << ", fim: " << fim << ", aux: "; for (auto x : aux) cerr << x << " "; cerr << '\n';
		if (askQuery(a, aux)) fim = m;
		else ini = m+1;
	}
	// cerr << "b: " << b[fim] << ", v: " << v[b[fim]] << '\n';

	return make_pair(v[b[fim]], v[(b[fim]^diff)]);
}

int bb(int c1, int c2)
{
	int a[nodes[c1].size()]; for (int i = 0; i < nodes[c1].size(); i++) a[i] = nodes[c1][i];
	int ini = 0, fim = nodes[c2].size()-1;
	while (ini < fim)
	{
		int m = (ini + fim) >> 1;
		int aux[m-ini+1];
		for (int i = ini; i <= m; i++) aux[i-ini] = nodes[c2][i];
		// cerr << "ini: " << ini << ", m: " << m << ", fim: " << fim << ", aux: "; for (auto x : aux) cerr << x << " "; cerr << '\n';
		if (query(nodes[c1].size(), m-ini+1, a, aux)) fim = m;
		else ini = m+1;
	}
	return nodes[c2][fim];
}

void run(int N)
{
	pai.resize(N+1); iota(pai.begin(), pai.end(), 0);
	sub.resize(N+1); fill(sub.begin(), sub.end(), 1);
	nodes.resize(N+1, vector<int>(1)); for (int i = 1; i <= N; i++) nodes[i][0] = i;

	for (int q = 1; q < N; q++)
	{
		vector<int> comps; comps.reserve(N-q+1);
		for (int i = 1; i <= N; i++) if (find(i) == i) comps.push_back(i);
		auto [c1, c2] = findComps(comps);
		// cerr << "c1: " << c1 << ", nodes: "; for (auto x : nodes[c1]) cerr << x << " "; cerr << '\n';
		// cerr << "c2: " << c2 << ", nodes: "; for (auto x : nodes[c2]) cerr << x << " "; cerr << '\n';
		int X = bb(c1, c2), Y = bb(c2, c1);
		setRoad(X, Y);
		une(X, Y);
	}
}

Compilation message

icc.cpp: In function 'int bb(int, int)':
icc.cpp:79:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  int a[nodes[c1].size()]; for (int i = 0; i < nodes[c1].size(); i++) a[i] = nodes[c1][i];
      |                                           ~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Ok! 116 queries used.
2 Correct 5 ms 592 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Ok! 631 queries used.
2 Correct 21 ms 760 KB Ok! 529 queries used.
3 Correct 23 ms 764 KB Ok! 575 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 592 KB Ok! 1569 queries used.
2 Correct 60 ms 636 KB Ok! 1304 queries used.
3 Correct 71 ms 592 KB Ok! 1543 queries used.
4 Correct 71 ms 636 KB Ok! 1478 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 592 KB Ok! 1523 queries used.
2 Correct 76 ms 760 KB Ok! 1521 queries used.
3 Correct 71 ms 592 KB Ok! 1516 queries used.
4 Correct 85 ms 592 KB Ok! 1555 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 760 KB Ok! 1491 queries used.
2 Correct 71 ms 592 KB Ok! 1476 queries used.
3 Correct 75 ms 640 KB Ok! 1439 queries used.
4 Correct 81 ms 592 KB Ok! 1508 queries used.
5 Correct 71 ms 760 KB Ok! 1566 queries used.
6 Correct 68 ms 760 KB Ok! 1490 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 592 KB Ok! 1473 queries used.
2 Correct 71 ms 636 KB Ok! 1466 queries used.