Submission #36790

#	Time	Username	Problem	Language	Result	Execution time	Memory
36790		aome	ICC (CEOI16_icc)	C++14	100 / 100	193 ms	2216 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int N = 105;

int par[N];
vector<int> vec[N];

int find(int u) {
	return (u == par[u]) ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	u = find(u), v = find(v);
	if (vec[u].size() > vec[v].size()) swap(u, v);
	for (auto i : vec[u]) vec[v].push_back(i);
	par[u] = v, vec[u].clear();
}

bool query(vector<int> a, vector<int> b) {
	int sza = a.size(), szb = b.size();
	int A[N], B[N];
	for (int i = 0; i < sza; ++i) A[i] = a[i];
	for (int i = 0; i < szb; ++i) B[i] = b[i]; 
	return query(sza, szb, A, B);
}

void find(int l, int r, vector<int> &go, vector<int> &to) {
	if (l == r) {
		int tmp = go[l]; go.clear(); go.push_back(tmp); return;
	}
	int mid = (l + r) >> 1;
	vector<int> a, b; b = to;
	for (int i = l; i <= mid; ++i) a.push_back(go[i]);
	if (query(a, b)) find(l, mid, go, to);
	else find(mid + 1, r, go, to);
}

void cal(vector<int> vx, vector<int> vy) {
	find(0, vx.size() - 1, vx, vy);
	find(0, vy.size() - 1, vy, vx);
	setRoad(vx[0], vy[0]), join(vx[0], vy[0]);
}

void run(int n) {
	for (int i = 1; i <= n; ++i) par[i] = i, vec[i].push_back(i);
	while (1) {
		vector<int> go;
		for (int i = 1; i <= n; ++i) {
			if (find(i) == i) go.push_back(i);
		}
		int sz = go.size();
		for (int i = 0; (1 << i) < sz; ++i) {
			vector<int> a, b;
			for (int j = 0; j < sz; ++j) {
				if (j >> i & 1) {
					for (auto k : vec[go[j]]) a.push_back(k);
				}
				else {
					for (auto k : vec[go[j]]) b.push_back(k);
				}
			}
			if (query(a, b)) {
				cal(a, b); break;
			}
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10