제출 #1117006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117006		ThegeekKnight16	ICC (CEOI16_icc)	C++17	100 / 100	86 ms	764 KiB

icc

#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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10