oj.uz

Submission #410311

# Submission time Handle Problem Language Result Execution time Memory
410311 2021-05-22T13:16:29 Z Blagojce ICC (CEOI16_icc) C++11
61 / 100
 211 ms 580 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define all(v) begin(v), end(v)
#define pq priority_queue
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int mxn = 2e2;

mt19937 _rand(time(NULL));

#include "icc.h"



int link[mxn];
int siz[mxn];
int n;

int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}

void unite(int a, int b){
	a = findx(a);
	b = findx(b);
	if(a == b) return;
	
	if(siz[a] < siz[b]) swap(a, b);
	siz[a] += siz[b];
	link[b] = a;
}



vector<int> unzip(vector<int> v){
	fr(i, 0, n){
		if(find(all(v), findx(i)) != v.end()) v.pb(i);
	}
	return v;
}

int QUERY(vector<int> v1, vector<int> v2){
	int N = (int)v1.size();
	int M = (int)v2.size();
	int a1[N];
	fr(i, 0, N) a1[i] = v1[i]+1;
	int a2[M];
	fr(i, 0, M) a2[i] = v2[i]+1;
	return query(N, M, a1, a2);
}


void separation(vector<int> v, vector<int> &a, vector<int> &b){
	random_shuffle(all(v));
	if(_rand()%2){
		for(int i = 0; (1<<i) < (int)v.size(); i ++){
			a.clear();
			b.clear();
			fr(j, 0, (int)v.size()){
				if(j&(1<<i)){
					a.pb(v[j]);
				}
				else{
					b.pb(v[j]);
				}
			}		
			vector<int> ua = unzip(a);
			vector<int> ub = unzip(b);
			if(QUERY(ua, ub)) break;
		}
	}
	else{
		for(int i = log2((int)v.size()); i >= 0; i --){
			a.clear();
			b.clear();
			fr(j, 0, (int)v.size()){
				if(j&(1<<i)){
					a.pb(v[j]);
				}
				else{
					b.pb(v[j]);
				}
			}		
			vector<int> ua = unzip(a);
			vector<int> ub = unzip(b);
			if(QUERY(ua, ub)) break;
		}
	}
}

int findvertex(vector<int> v, vector<int> stat){
	if((int)v.size() == 1){
		return v[0];
	}
	vector<int> lh;
	vector<int> rh;
	fr(i, 0, (int)v.size()/2){
		lh.pb(v[i]);
	}
	fr(i,(int)v.size()/2, (int)v.size()){
		rh.pb(v[i]);
	}
	if(QUERY(lh, stat)){
		return findvertex(lh, stat);
	}
	else{
		return findvertex(rh, stat);
	}
}
void run(int N){
	n = N;
	fr(i, 0, n) link[i] = i, siz[i] = 1;
	fr(i, 0, n-1){
		vector<int> v;
		fr(p, 0, n){
			v.pb(findx(p));
		}
		sort(all(v));
		v.erase(unique(all(v)),v.end());
		
		vector<int> v1;
		vector<int> v2;
		separation(v, v1, v2);
		
		v1 = unzip(v1);
		v2 = unzip(v2);
		
		int U = findvertex(v1, v2);
		int V = findvertex(v2,{U});
		
		setRoad(U+1, V+1);
		unite(U, V);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Ok! 121 queries used.
2 Correct 8 ms 500 KB Ok! 123 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 492 KB Ok! 612 queries used.
2 Correct 55 ms 492 KB Ok! 737 queries used.
3 Correct 56 ms 460 KB Ok! 747 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 548 KB Ok! 1574 queries used.
2 Correct 191 ms 512 KB Ok! 1784 queries used.
3 Correct 180 ms 508 KB Ok! 1665 queries used.
4 Correct 181 ms 524 KB Ok! 1699 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 560 KB Ok! 1736 queries used.
2 Correct 197 ms 548 KB Ok! 1699 queries used.
3 Correct 190 ms 580 KB Ok! 1772 queries used.
4 Correct 165 ms 548 KB Ok! 1608 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 540 KB Too many queries! 1785 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 552 KB Too many queries! 1772 out of 1625
2 Halted 0 ms 0 KB -