Submission #95176

#	Time	Username	Problem	Language	Result	Execution time	Memory
95176		jasony123123	ICC (CEOI16_icc)	C++11	100 / 100	136 ms	632 KiB

icc

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include "icc.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/******************************CEOI 2016 Day 1 P1 - ICC*********************************/

v<int> adj[101];
v<v<int>> comp;
int N, M;

v<int> unpack(v<int> &compA) {
	v<int> nodeA;
	for (auto c : compA) for (auto x : comp[c])
		nodeA.push_back(x);
	return nodeA;
}

int queryNodes(v<int> nodeA, v<int> nodeB) {
	return query(nodeA.size(), nodeB.size(), nodeA.data(), nodeB.data());
}

int queryComp(v<int> &compA, v<int> &compB) {
	return queryNodes(unpack(compA), unpack(compB));
}


void dfs(int x, v<bool> &vis, v<int> &rec) {
	if (vis[x]) return;
	vis[x] = 1;
	rec.push_back(x);
	for (auto c : adj[x]) dfs(c, vis, rec);
}

void updComp() {
	v<bool> vis(N + 1, 0);
	comp.clear();
	FORE(i, 1, N) if (!vis[i]) {
		comp.push_back(v<int>());
		dfs(i, vis, comp.back());
	}
	M = comp.size();
}

void findConnectComp(v<int> &compA, v<int> &compB) {
	FOR(b, 0, 8) {
		v<int> ca, cb;
		FOR(i, 0, M) {
			if (i&(1 << b)) ca.push_back(i);
			else cb.push_back(i);
		}
		if (!ca.empty() && !cb.empty() && queryComp(ca, cb)) {
			compA = ca, compB = cb;
			return;
		}
	}
}

void reduce(v<int> &noa, v<int> &nob) {
	while (nob.size() > 1) {
		v<int> top, bot;
		int mid = (0 + nob.size() - 1) / 2;
		FORE(i, 0, mid)
			top.push_back(nob[i]);
		FORE(i, mid + 1, nob.size() - 1)
			bot.push_back(nob[i]);

		if (queryNodes(noa, top))
			nob = top;
		else
			nob = bot;
	}
}

void run(int n) {
	N = n;
	FOR(r, 0, n - 1) {
		updComp();

		v<int> compA, compB;
		findConnectComp(compA, compB);

		v<int> nodeA = unpack(compA);
		v<int> nodeB = unpack(compB);
		reduce(nodeA, nodeB);
		reduce(nodeB, nodeA);

		setRoad(nodeA[0], nodeB[0]);
		adj[nodeA[0]].push_back(nodeB[0]);
		adj[nodeB[0]].push_back(nodeA[0]);
	}
}

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