oj.uz

Submission #403937

# Submission time Handle Problem Language Result Execution time Memory
403937 2021-05-13T15:24:12 Z CaroLinda ICC (CEOI16_icc) C++14
100 / 100
 148 ms 500 KB 
#include "icc.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define ll long long
#define ff first
#define ss second

const int MAX = 110 ;

using namespace std ;

int N ;
int dsu[MAX] ;
vector<int> a , b ;

int find(int x) { return dsu[x] = (x == dsu[x]) ? x : find(dsu[x]) ; }
void join(int x, int y)
{
	x = find(x) ;
	y = find(y) ;

	if(x == y) return ;

	if( x < y ) dsu[y] = x ;
	else dsu[x] = y ;
}

bool ask()
{
	if( !sz(a) || !sz(b) ) return false ;

	int A[ sz(a) ] ;
	int B[sz(b)] ;

	for(int i = 0 ; i < sz(a) ; i++ ) A[i] = a[i]+1 ;
	for(int i = 0 ; i < sz(b) ; i++ ) B[i] = b[i]+1 ;

	return query( sz(a) , sz(b) , A , B ) ;

}

void solve()
{
	vector< vector<int> > vec ;

	for(int i = 0 ; i < N ; i++ )
	{
		if(i != find(i)) continue ;

		vec.push_back(vector<int>()) ;

		for(int j = 0 ; j < N ; j++ )
			if( find(j) == i ) vec.back().push_back(j) ;
	}

	int H = sz(vec) , x = 0 ;

	for(int i = 0 ; (1<<i) < H ; i++ )
	{
		a.clear() ;
		b.clear() ;

		for(int j = 0 ; j < H ; j++ )
		{
			if( j&(1<<i) ) a.insert(a.end() , vec[j].begin() , vec[j].end() ) ;
			else b.insert( b.end() , vec[j].begin() , vec[j].end() ) ;
		}

		if( ask() ) x ^= (1<<i) ;
	}

	vector< pair<int,int> > pairs ;

	for(int i = 0 ; i < H ; i++ )
		if( (i^x) < H && i < (i^x) ) pairs.push_back( make_pair(i, i^x) ) ;

	while( sz(pairs) > 1 )
	{

		a.clear() ;
		b.clear() ;

		for(int i = 0 ; i < sz(pairs)/2 ; i++ ) 
		{
			a.insert( a.end() , vec[ pairs[i].first ].begin() , vec[ pairs[i].first ].end() ) ;
			b.insert( b.end() , vec[ pairs[i].second ].begin() , vec[ pairs[i].second ].end() ) ;
		}

		if( ask() ) pairs = vector<pair<int,int> >( pairs.begin() , pairs.begin()+sz(pairs)/2 ) ;
		else pairs = vector<pair<int,int> >( pairs.begin()+sz(pairs)/2 , pairs.end() ) ;

	}

	vector<int> c = vector<int>( vec[ pairs[0].first ].begin() , vec[ pairs[0].first ].end() ) ;
	vector<int> d = vector<int>( vec[pairs[0].second].begin()  , vec[pairs[0].second].end() ) ;

	while( true )
	{
		if( sz(c) < sz(d) ) swap(c,d) ;
		if( sz(c) == 1 )
		{
			setRoad(c[0]+1, d[0]+1) ;
			join(c[0] , d[0]) ;
			return ;
		}

		a.clear() ;
		b.clear() ;

		a = vector<int>( c.begin() ,c.begin()+sz(c)/2 ) ;
		b = d ;

		if(ask()) c = a ;
		else c = vector<int>( c.begin()+sz(c)/2 , c.end() ) ;
	}

}

void run(int n)
{
	N = n ;

	for(int i = 0 ; i < N ; i++  ) dsu[i] = i ;
	for(int i = 0 ; i < N-1 ; i++ ) solve() ;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Ok! 111 queries used.
2 Correct 7 ms 460 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 488 KB Ok! 609 queries used.
2 Correct 43 ms 460 KB Ok! 493 queries used.
3 Correct 37 ms 460 KB Ok! 538 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 488 KB Ok! 1500 queries used.
2 Correct 115 ms 484 KB Ok! 1145 queries used.
3 Correct 132 ms 488 KB Ok! 1523 queries used.
4 Correct 135 ms 460 KB Ok! 1534 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 500 KB Ok! 1458 queries used.
2 Correct 135 ms 488 KB Ok! 1493 queries used.
3 Correct 148 ms 484 KB Ok! 1490 queries used.
4 Correct 148 ms 492 KB Ok! 1525 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 496 KB Ok! 1470 queries used.
2 Correct 132 ms 500 KB Ok! 1508 queries used.
3 Correct 131 ms 480 KB Ok! 1415 queries used.
4 Correct 140 ms 484 KB Ok! 1520 queries used.
5 Correct 135 ms 420 KB Ok! 1543 queries used.
6 Correct 135 ms 484 KB Ok! 1532 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 484 KB Ok! 1432 queries used.
2 Correct 122 ms 484 KB Ok! 1266 queries used.