oj.uz

Submission #139955

# Submission time Handle Problem Language Result Execution time Memory
139955 2019-08-01T17:49:50 Z aminra ICC (CEOI16_icc) C++17
100 / 100
 156 ms 764 KB 
#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;
/*void setRoad(int a, int b)
{
	cout << "edge is ---> " << a << " " << b << endl;
}
int query(int size_a, int size_b, int a[], int b[])
{
	cout << "Ask ---> " << size_a << " " << size_b << endl;
	for (int i = 0; i < size_a; i++)
		cout << a[i] << " ";
	cout << "\n";
	for (int i = 0; i < size_b; i++)
		cout << b[i] << " ";
	cout << endl;
	int ans;
	cin >> ans;
	return ans;
}*/
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);
}
/*int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	run(4);
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 110 queries used.
2 Correct 10 ms 632 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 632 KB Ok! 611 queries used.
2 Correct 41 ms 504 KB Ok! 504 queries used.
3 Correct 43 ms 504 KB Ok! 539 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 764 KB Ok! 1515 queries used.
2 Correct 132 ms 652 KB Ok! 1206 queries used.
3 Correct 151 ms 568 KB Ok! 1539 queries used.
4 Correct 150 ms 564 KB Ok! 1509 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 508 KB Ok! 1515 queries used.
2 Correct 153 ms 504 KB Ok! 1516 queries used.
3 Correct 154 ms 564 KB Ok! 1488 queries used.
4 Correct 153 ms 604 KB Ok! 1534 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 600 KB Ok! 1456 queries used.
2 Correct 155 ms 560 KB Ok! 1506 queries used.
3 Correct 146 ms 508 KB Ok! 1356 queries used.
4 Correct 156 ms 576 KB Ok! 1519 queries used.
5 Correct 149 ms 504 KB Ok! 1528 queries used.
6 Correct 152 ms 560 KB Ok! 1533 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 632 KB Ok! 1376 queries used.
2 Correct 137 ms 504 KB Ok! 1270 queries used.