Submission #253870

#	Time	Username	Problem	Language	Result	Execution time	Memory
253870		Lawliet	통행료 (IOI18_highway)	C++17	18 / 100	386 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 90010;
const int MAXM = 130010;

int n, m;
int A, B;

int color[MAXN];
int U[MAXM], V[MAXM];

vector< vector<int> > groups;

bool sameGroup()
{
	vector<int> q( m , 0 );

	for(int i = 0 ; i < m ; i++)
		if( color[ U[i] ] == color[ V[i] ] ) q[i] = 1;

	return ( ask(q)%2 == 0 );
}

void splitVector(vector<int>& v, vector<int>& L, vector<int>& R)
{
	int m = (int)v.size()/2;

	for(int i = 0 ; i < m ; i++)
		L.push_back( v[i] );

	for(int i = m ; i < (int)v.size() ; i++)
		R.push_back( v[i] );
}

void splitGroups()
{
	vector< vector<int> > aux( 2*groups.size() );

	for(int i = 0 ; i < (int)groups.size() ; i++)
		splitVector( groups[i] , aux[2*i] , aux[2*i + 1] );
	
	groups = aux;
}

void paintGroup(vector<int>& nodes, int c)
{
	for(int i = 0 ; i < (int)nodes.size() ; i++)
		color[ nodes[i] ] = c;
}

void divideGroups()
{
	while( true )
	{
		splitGroups();

		for(int i = 0 ; i < (int)groups.size() ; i++)
			paintGroup( groups[i] , i%2 );

		if( !sameGroup() ) break;
	}
}

bool testGroup(int k)
{
	for(int i = 0 ; i < (int)groups.size() ; i++)
		paintGroup( groups[i] , 0 );

	for(int i = 0 ; i <= k ; i += 2)
		paintGroup( groups[i] , 1 );

	return !sameGroup();
}

int bsGroup()
{
	int l = 0;
	int r = ( (int)groups.size() - 1 )/2;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( testGroup( 2*m ) ) r = m;
		else l = m + 1;
	}

	return 2*r;
}

bool testNode(int g, int k)
{
	for(int i = 0 ; i <= k ; i++)
		color[ groups[g][i] ] = 1;

	for(int i = k + 1 ; i < (int)groups[g].size() ; i++)
		color[ groups[g][i] ] = 0;

	return sameGroup();
}

int bsNode(int g)
{
	int l = 0;
	int r = (int)groups[g].size() - 1;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( testNode( g , m ) ) r = m;
		else l = m + 1;
	}

	return groups[g][r];
}

void find_pair(int N, vector<int> u, vector<int> v, int a, int b) 
{
	A = a; B = b;
	n = N; m = (int)u.size();

	for(int i = 0 ; i < m ; i++)
		U[i] = u[i], V[i] = v[i];

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

	for(int i = 0 ; i < n ; i++)
		groups[0].push_back( i );

	divideGroups();

	int groupS = bsGroup();
	int groupT = groupS + 1;

	for(int i = 0 ; i < (int)groups.size() ; i++)
		paintGroup( groups[i] , 0 );

	paintGroup( groups[groupT] , 1 );

	int S = bsNode( groupS );

	paintGroup( groups[groupS] , 0 );
	paintGroup( groups[groupT] , 0 );

	color[S] = 1;

	int T = bsNode( groupT );

	answer( S , T );
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 18 / 18
• Subtask 6: 0 / 31