Submission #24524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24524	2017-06-09T18:27:21 Z	rubabredwan	ICC (CEOI16_icc)	C++14	100 / 100	153 ms	2272 KB

icc

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;
 
const int N = 105;
 
int n, par[N], mat[N][N];
set<int>comp;
vector<int>nudes[N];
 
int Find(int at){
	return par[at] == at ? at : par[at] = Find(par[at]);
}
 
void Union(int a, int b){
	int x = Find(a);
	int y = Find(b);
	for(auto u : nudes[y]){
		nudes[x].push_back(u);
	}
	par[y] = x;
	comp.erase(y);
}

 
int fuk[N], tt;
 
int get(int sa, int sb, int a[], int b[]){
	int lo = 0, hi = sb - 1;
	while(lo < hi){
		int mid = (lo + hi) / 2; tt = 0;
		for(int i=lo;i<=mid;i++) fuk[tt] = b[i], ++tt;
		if(query(sa, tt, a, fuk)) hi = mid;
		else lo = mid + 1;
	}
	return b[lo];
}
 
int aa[N], bb[N], cr[N];
int sa, sb, sz;
 
void run(int _n){
	srand(time(NULL));
	n = _n;
	comp.clear();
	for(int i=1;i<=n;i++){
		par[i] = i;
		comp.insert(i);
		nudes[i].push_back(i);
	}
	for(int road = 1; road < n; ++road){
		sz = 0;
		for(auto u : comp) cr[++sz] = u;
		for(int bit = 0; bit <= 7; ++bit){
			sa = 0, sb = 0;
			for(int i = 1; i <= sz; ++i){
				if(i & (1 << bit)) for(auto v : nudes[cr[i]]) aa[sa] = v, ++sa;
				else for(auto v : nudes[cr[i]]) bb[sb] = v, ++sb;
			}
			if(sa == 0 || sb == 0) continue;
			if(query(sa, sb, aa, bb)){
				int x = get(sa, sb, aa, bb);
				int y = get(sb, sa, bb, aa);
				Union(x, y);
				setRoad(x, y);
				break;
			}
		}
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	2132 KB	Ok! 98 queries used.
2	Correct	6 ms	2136 KB	Ok! 99 queries used.

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	2140 KB	Ok! 532 queries used.
2	Correct	46 ms	2140 KB	Ok! 647 queries used.
3	Correct	63 ms	2136 KB	Ok! 652 queries used.

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	2268 KB	Ok! 1385 queries used.
2	Correct	153 ms	2268 KB	Ok! 1608 queries used.
3	Correct	143 ms	2272 KB	Ok! 1601 queries used.
4	Correct	136 ms	2268 KB	Ok! 1498 queries used.

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	2268 KB	Ok! 1491 queries used.
2	Correct	136 ms	2264 KB	Ok! 1484 queries used.
3	Correct	136 ms	2272 KB	Ok! 1566 queries used.
4	Correct	153 ms	2268 KB	Ok! 1444 queries used.

Subtask #5

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	2268 KB	Ok! 1559 queries used.
2	Correct	146 ms	2268 KB	Ok! 1579 queries used.
3	Correct	143 ms	2268 KB	Ok! 1616 queries used.
4	Correct	136 ms	2264 KB	Ok! 1587 queries used.
5	Correct	126 ms	2268 KB	Ok! 1442 queries used.
6	Correct	136 ms	2268 KB	Ok! 1537 queries used.

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	2268 KB	Ok! 1586 queries used.
2	Correct	143 ms	2268 KB	Ok! 1608 queries used.