oj.uz

Submission #56371

# Submission time Handle Problem Language Result Execution time Memory
56371 2018-07-11T07:30:54 Z Yehezkiel ICC (CEOI16_icc) C++11
100 / 100
 198 ms 940 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> pii;
const int MAXN=100;
int par[MAXN+5],n;
int finds(int x){
	if(par[x]!=x)
		par[x]=finds(par[x]);
	return par[x];
}
bool connected(int u,int v){
	return (finds(u)==finds(v));
}
void gabung(int u,int v){
	u=finds(u),v=finds(v);
	if(u==v)
		return;
	par[v]=u;
}

int tanya(vector <int> a,vector <int> b){				//O(N)
	int arr1[105];int arr2[105];
	for(int i=0;i<(int) a.size();i++)
		arr1[i]=a[i];
	for(int i=0;i<(int) b.size();i++)
		arr2[i]=b[i];
	
	return query(a.size(),b.size(),arr1,arr2);
}
void expand(vector <int> &vec){		//isinya cuman kepala suku	O(N)
	bool root[MAXN+5];
	for(int i=1;i<=n;i++)
		root[i]=false;
	for(auto isi:vec)
	{
		root[isi]=true;
		assert(isi==par[isi]);
	}
	vec.clear();
	for(int i=1;i<=n;i++)
		if(root[finds(i)])
			vec.pb(i);
}
void masukkan(vector <int> &tampung,const vector <int> tambahan){
	for(int isi:tambahan)
		tampung.pb(isi);
}

int perkecil(vector <int> now,const vector <int> other){			//Query(now,other) is 1, we only need to find the right "now"
	vector <int> temp;
	while(now.size()>1)				//O(logN)
	{
		temp.clear();
		for(int i=now.size()/2;i<(int) now.size();i++)
			temp.pb(now[i]);
		now.resize(now.size()/2);
		
		if(tanya(now,other)==0)				//O(N)
			now=temp;
	}
	return now[0];				//when only one possibility exist, it must be the right now
}

void bagiDua(vector <int> &vec,int &lebih,vector<vector<int> > &tampung){
	random_shuffle(all(vec));					//Just for Optimization
	int ambil=vec.size()/2;
	if(lebih&&(vec.size()&1))
		lebih--,ambil++;
	
	vector <int> kiri,kanan;
	for(int i=0;i<(int) vec.size();i++)
		(i<ambil)?kiri.pb(vec[i]):kanan.pb(vec[i]);
	tampung.pb(kiri);tampung.pb(kanan);
}
vector <int> kiri,kanan,possible[MAXN+5];
void findAnggota(){
	vector <vector <int> > anggota,baru;
	anggota.resize(1);
	for(int i=1;i<=n;i++)
	{
		if(par[i]==i)					//the head of component
			anggota[0].pb(i);
	}
	while(true)
	{
		baru.clear();
		int lebih=0;						//to Divide the odd element equally
		for(auto &isi:anggota)
			lebih+=isi.size()%2;
		lebih/=2;
		
		for(auto &isi:anggota)
			bagiDua(isi,lebih,baru);
		assert(lebih==0);
		
		kiri.clear();kanan.clear();
		for(int i=0;i<(int) baru.size();i++)
			(i&1)?masukkan(kanan,baru[i]):masukkan(kiri,baru[i]);
		assert(abs((int) kiri.size() - (int) kanan.size())<=1);
		
		expand(kiri),expand(kanan);
		if(tanya(kiri,kanan))
			break;
		
		anggota=baru;
	}
	
	//Find Possibility, For Optimization
	for(int i=0;i<(int) baru.size();i+=2)
	{
		assert(i+1<(int) baru.size());
		for(auto isi:baru[i])
		{
			possible[isi].clear();
			masukkan(possible[isi],baru[i+1]);
		}
	}
}
void run(int _n){
	srand(2305);
	n=_n;
	for(int i=1;i<=n;i++)
		par[i]=i;
	
	for(int i=0;i<n-1;i++)
	{
		findAnggota();
		
		pii ans;
		ans.fi=perkecil(kiri,kanan);
		kanan=possible[finds(ans.fi)];
		expand(kanan);
		ans.se=perkecil(kanan,kiri);
		
		setRoad(ans.fi,ans.se);
		gabung(ans.fi,ans.se);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 540 KB Ok! 94 queries used.
2 Correct 10 ms 612 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 660 KB Ok! 510 queries used.
2 Correct 58 ms 660 KB Ok! 515 queries used.
3 Correct 61 ms 736 KB Ok! 536 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 740 KB Ok! 1292 queries used.
2 Correct 171 ms 784 KB Ok! 1245 queries used.
3 Correct 171 ms 848 KB Ok! 1367 queries used.
4 Correct 165 ms 848 KB Ok! 1319 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 872 KB Ok! 1333 queries used.
2 Correct 165 ms 872 KB Ok! 1281 queries used.
3 Correct 196 ms 872 KB Ok! 1353 queries used.
4 Correct 167 ms 872 KB Ok! 1326 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 872 KB Ok! 1338 queries used.
2 Correct 172 ms 872 KB Ok! 1336 queries used.
3 Correct 198 ms 872 KB Ok! 1335 queries used.
4 Correct 161 ms 872 KB Ok! 1315 queries used.
5 Correct 169 ms 940 KB Ok! 1318 queries used.
6 Correct 188 ms 940 KB Ok! 1319 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 940 KB Ok! 1337 queries used.
2 Correct 151 ms 940 KB Ok! 1266 queries used.