Submission #139956

#	Time	Username	Problem	Language	Result	Execution time	Memory
139956		aminra	ICC (CEOI16_icc)	C++17	100 / 100	155 ms	632 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)103;
const ll infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18 + 3;
vector<int> comp[MAXN];
int par[MAXN];
int get(int a)
{
	if(par[a] == a)
		return a;
	return par[a] = get(par[a]);
}
void merge(int a, int b)
{
	if((a = get(a)) == (b = get(b)))
		return;
	if(comp[a].size() < comp[b].size())
		swap(a, b);
	par[b] = a;
	for (auto u : comp[b])
		comp[a].push_back(u);
	comp[b].clear();
}
void solve(int n)
{
	vector<int> mai;
	for (int i = 1; i <= n; i++)
		if(par[i] == i)
			mai.push_back(i);
	int lg = 0, idx = 1, sz = mai.size();
	while(idx <= sz)
		idx <<= 1, lg++;
	lg--;
	int xo = 0;
	for (int i = 0; i <= lg; i++)
	{
		vector<int> query0, query1;
		for (int j = 0; j < sz; j++)
			if((j >> i) & 1)	
			{
				for (auto x : comp[mai[j]])
					query1.push_back(x);
			}
			else
			{
				for (auto x : comp[mai[j]])
					query0.push_back(x);
			}
		int ans = 0;
		if(query0.size() && query1.size())
			ans = query(query0.size(), query1.size(), query0.data(), query1.data());
		if(ans == 1)
			xo += (1 << i);
	}
	vector<pair<int, int> > matching;
	for (int i = 0; i < sz; i++)	
	{
		int match = (i ^ xo);
		if(match < sz && i < match)
			matching.push_back({i, match});
	}	
	sz = matching.size();
	int L = -1, R = sz - 1;
	while(R - L > 1)
	{
		int mid = (L + R) >> 1;
		vector<int> query0, query1;
		for (int i = 0; i <= mid; i++)	
		{
			int id0 = mai[matching[i].first];
			for (auto x : comp[id0])
				query0.push_back(x);
			int id1 = mai[matching[i].second];
			for (auto x : comp[id1])
				query1.push_back(x);
		}
		int ans = query(query0.size(), query1.size(), query0.data(), query1.data());
		if(ans == 1)	
			R = mid;
		else
			L = mid;
	}
	int x = mai[matching[R].first], y = mai[matching[R].second];
	vector<int> cmp[2];
	for (auto u : comp[x])
		cmp[0].push_back(u);
	for (auto u : comp[y])
		cmp[1].push_back(u);
	for (int j = 0; j < 2; j++)
	{
		while(cmp[j].size() > 1)
		{
			int ans = query(cmp[j].size() / 2, cmp[j ^ 1].size(), cmp[j].data(), cmp[j ^ 1].data());
			if(ans)
				cmp[j].erase(cmp[j].begin() + cmp[j].size() / 2, cmp[j].end());
			else
				cmp[j].erase(cmp[j].begin(), cmp[j].begin() + cmp[j].size() / 2);
		}
	}
	int u = cmp[0][0], v = cmp[1][0];
	setRoad(u, v);
	merge(u, v);
	return;
}
void run(int n)
{
	for (int i = 1; i <= n; i++)
		par[i] = i, comp[i].push_back(i);
	int edges = n - 1;
	while(edges--)
		solve(n);
}

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