oj.uz

Submission #259355

# Submission time Handle Problem Language Result Execution time Memory
259355 2020-08-07T16:30:23 Z youssefbou62 ICC (CEOI16_icc) C++14
18 / 100
 562 ms 632 KB 
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;


#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
#define sz(x)  (int)x.size() 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int MAXN = 105 ; 
int n ; 
int par[MAXN]; 
vector<int> groups , inG[MAXN]; 
void init(int N){
	for(int i = 1 ; i  <= N ; i++ )par[i] = i , groups.pb(i),inG[i].pb(i); 
}

int fs(int u){
	if( par[u] == u )return u; 
	return par[u] = fs(par[u]) ; 
}

void us(int u,int v){
	u = fs(u) ; 
	v = fs(v) ; 
	if( u == v )return ; 
	par[u] = v ;
	for(int x : inG[u])
		inG[v].pb(x) ; 
}

// int query(int size_a, int size_b, int a[], int b[]){
// 	cout << "QUERY *********"<<endl; 
// 	cout << size_a << endl; 
// 	for(int i = 0 ; i < size_a ; i++ )cout << a[i] << " " ;cout << endl; 
// 	cout << size_b << endl; 
// 	for(int i = 0 ; i < size_b ; i++ )cout << b[i] << " " ;cout << endl; 
// 	bool x ;
// 	cin >> x ; 
// 	return x ;
// }	

// void setRoad(int a, int b){
// 	cout << "setRoad "<< a << " " << b << endl;
// return ; 
// }

void run(int N){
	n = N ; 
	init(n); 
	int a[N],b[N],c[N],d[N]; 
	for(int i = 0 ; i < n - 1 ; i++ ){
		int res1 = -1 , res2 = -1 ;
		int cnt = 0 ; 
		for(int j = 0 ; j < sz(groups) ; j++ ){
			int cnt1 = 0 ; 
			for(int  x = j + 1 ; x < sz(groups) ; x++ )for(int y : inG[groups[x]] ) b[cnt1] = y , cnt1 ++ ; 
			
				bool stop = 0;
				for(int y : inG[groups[j]]){
					a[cnt] = y; 
					cnt++; 
			
					if( query(cnt,cnt1,a,b) ) {
						res1 = y ;
						c[0] =  y ; 
						int l = 0 , r = cnt1-1 ; 
						while ( l <=  r ){
							int mid = ( l + r )/ 2 ; 
							int yy = 0 ; 
							for(int x = l  ; x <= mid ;x++ ){
								d[yy] = b[x] ; 
								yy ++ ; 
							}
							if(query(1,yy,c,d))
								r = mid - 1, res2 = b[mid] ;  
							else l = mid + 1 ; 
						}

						stop = 1;
						break ; 
					}
				
			}
			if(stop)break; 

		}
		setRoad(res1,res2); 
		us(res1,res2); 
		groups.clear(); 
		for(int i = 1 ; i <= n ; i++ )
			if( find(all(groups),fs(i))== groups.end() )
				groups.pb(fs(i)) ; 
	
	}
}


// int main(){
// 	cin >> n ; 
// 	run(n) ; 
// }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Ok! 154 queries used.
2 Correct 13 ms 512 KB Ok! 163 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 512 KB Ok! 1942 queries used.
2 Correct 152 ms 632 KB Ok! 1487 queries used.
3 Correct 132 ms 512 KB Ok! 1452 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 562 ms 632 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 512 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 451 ms 556 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 512 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -