oj.uz

Submission #139106

# Submission time Handle Problem Language Result Execution time Memory
139106 2019-07-31T09:30:39 Z Mahdi_Jfri Highway Tolls (IOI18_highway) C++14
0 / 100
 26 ms 6128 KB 
#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] , 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;
		}
	}

	for(auto x : ax)
		cout << x << " ";
	cout << endl;

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5316 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5444 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6008 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5368 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6128 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6056 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -