Submission #706995

#	Time	Username	Problem	Language	Result	Execution time	Memory
706995		TranGiaHuy1508	ICC (CEOI16_icc)	C++17	100 / 100	132 ms	500 KiB

icc

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

#include "icc.h"

namespace local {
	int n;
	vector<int> V, parent;
	vector<vector<int>> groups;

	int get_parent(int x){
		if (x == parent[x]) return x;
		return parent[x] = get_parent(parent[x]);
	}

	void add_edge(int x, int y){
		setRoad(x, y);

		x = get_parent(x);
		y = get_parent(y);

		for (auto i: groups[y]) groups[x].push_back(i);
		groups[y].clear();
		parent[y] = x;

		vector<int> newv;
		for (auto i: V) if (i != y) newv.push_back(i);
		V.swap(newv);

	}

	void found_solve(vector<int> &g1, vector<int> &g2){
		vector<int> tmp;
		int l = 0, r = g1.size() - 1;
		while (l < r){
			int mid = (l + r) >> 1;
			tmp.clear(); for (int i = 0; i <= mid; i++) tmp.push_back(g1[i]);
			if (query(tmp.size(), g2.size(), &tmp[0], &g2[0])) r = mid;
			else l = mid + 1;
		}
		vector<int> result = {g1[r]};
		if (g2.size() > 1){
			found_solve(g2, result);
			return;
		}
		add_edge(result[0], g2[0]);
	}

	void normal_solve(vector<int> &v){
		for (int b = 0; b < 7; b++){
			vector<int> g1, g2;
			
			for (int i = 0; i < (int)v.size(); i++){
				if ((i >> b) & 1){
					for (auto j: groups[v[i]]) g1.push_back(j);
				}
				else{
					for (auto j: groups[v[i]]) g2.push_back(j);
				}
			}

			if (query(g1.size(), g2.size(), &g1[0], &g2[0])){
				found_solve(g1, g2);
				return;
			}
		}
	}
}

void run(int N){
	local::n = N;
	local::groups.resize(local::n + 1);
	local::parent.resize(local::n + 1);
	iota(local::parent.begin(), local::parent.end(), 0);
	local::V.resize(local::n);
	iota(local::V.begin(), local::V.end(), 1);

	for (int i = 1; i <= local::n; i++) local::groups[i].push_back(i);

	for (int i = 0; i < local::n - 1; i++){
		local::normal_solve(local::V);
	}
}

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