Submission #139109

#	Time	Username	Problem	Language	Result	Execution time	Memory
139109		Mahdi_Jfri	Highway Tolls (IOI18_highway)	C++14	51 / 100	253 ms	11948 KiB

highway

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

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 2e5 + 20;

bool hide[maxn];

int x , y , from[maxn] , to[maxn];

ll frst;

vector<int> adj[maxn] , tw;

bool is[maxn] , can[maxn];

void reval(int v)
{
	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;
		if(!hide[u])
			tw[e] = 1;
	}
}

bool diff()
{
	for(int i = 0; i < (int)tw.size(); i++)
		tw[i] = (is[from[i]] != is[to[i]]);

	return (((ask(tw) - frst) / (y - x)) % 2 == 1);
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B)
{
	x = A , y = B;

	int m = U.size();
	for(int i = 0; i < m; i++)
	{
		tw.pb(0);
		int a = U[i] , b = V[i];

		adj[a].pb(i);
		adj[b].pb(i);

		from[i] = a , to[i] = b;
	}

	frst = ask(tw);

	vector<int> ax , bx;
	for(int b = 0; b < 20; b++)
	{
		memset(is , 0 , sizeof is);
		for(int i = 0; i < n; i++)
			is[i] = bit(i , b);

		if(diff())
		{
			for(int i = 0; i < n; i++)
			{
				if(bit(i , b))
					ax.pb(i);
				else
					bx.pb(i);
			}
			break;
		}
	}

	memset(can , 1 , sizeof can);
	for(int b = 0; b < 20; b++)
	{
		if((1 << b) < (int)ax.size())
		{
			memset(is , 0 , sizeof is);
			for(int i = 0; i < (int)ax.size(); i++)
				is[ax[i]] = bit(i , b);

			if(diff())
			{
				for(int i = 0; i < (int)ax.size(); i++)
					if(!bit(i , b))
						can[ax[i]] = 0;
			}
			else
			{
				for(int i = 0; i < (int)ax.size(); i++)
					if(bit(i , b))
						can[ax[i]] = 0;
			}
		}

		if((1 << b) < (int)bx.size())
		{
			memset(is , 0 , sizeof is);
			for(int i = 0; i < (int)bx.size(); i++)
				is[bx[i]] = bit(i , b);

			if(diff())
			{
				for(int i = 0; i < (int)bx.size(); i++)
					if(!bit(i , b))
						can[bx[i]] = 0;
			}
			else
			{
				for(int i = 0; i < (int)bx.size(); i++)
					if(bit(i , b))
						can[bx[i]] = 0;
			}
		}
	}

	int S = -1 , T = -1;
	for(auto v : ax)
		if(can[v])
		{
			while(S != -1);
			S = v;
		}

	for(auto v : bx)
		if(can[v])
		{
			while(T != -1);
			T = v;
		}

	answer(S , T);
}

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