oj.uz

Submission #139107

# Submission time Handle Problem Language Result Execution time Memory
139107 2019-07-31T09:31:09 Z Mahdi_Jfri Highway Tolls (IOI18_highway) C++14
5 / 100
 222 ms 11640 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;
		}
	}

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5368 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 6 ms 5504 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 6 ms 5368 KB Output is correct
6 Correct 6 ms 5368 KB Output is correct
7 Correct 7 ms 5368 KB Output is correct
8 Correct 6 ms 5520 KB Output is correct
9 Correct 6 ms 5368 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5484 KB Output is correct
12 Correct 7 ms 5420 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5504 KB Output is correct
2 Correct 28 ms 6136 KB Output is correct
3 Correct 177 ms 11636 KB Output is correct
4 Correct 220 ms 11640 KB Output is correct
5 Correct 202 ms 11640 KB Output is correct
6 Correct 215 ms 11536 KB Output is correct
7 Correct 219 ms 11588 KB Output is correct
8 Correct 198 ms 11536 KB Output is correct
9 Correct 201 ms 11620 KB Output is correct
10 Correct 213 ms 11536 KB Output is correct
11 Correct 202 ms 11440 KB Output is correct
12 Correct 209 ms 11532 KB Output is correct
13 Correct 218 ms 11444 KB Output is correct
14 Incorrect 211 ms 11456 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6008 KB Output is correct
2 Correct 38 ms 6708 KB Output is correct
3 Correct 62 ms 7416 KB Output is correct
4 Correct 181 ms 11448 KB Output is correct
5 Correct 173 ms 11428 KB Output is correct
6 Correct 164 ms 11444 KB Output is correct
7 Correct 162 ms 11432 KB Output is correct
8 Correct 181 ms 11440 KB Output is correct
9 Incorrect 175 ms 11440 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5472 KB Output is correct
2 Correct 28 ms 6096 KB Output is correct
3 Correct 166 ms 10268 KB Output is correct
4 Correct 206 ms 11552 KB Output is correct
5 Correct 222 ms 11544 KB Output is correct
6 Correct 195 ms 11540 KB Output is correct
7 Correct 206 ms 11612 KB Output is correct
8 Correct 209 ms 11520 KB Output is correct
9 Correct 220 ms 11544 KB Output is correct
10 Correct 218 ms 11532 KB Output is correct
11 Correct 203 ms 11416 KB Output is correct
12 Incorrect 212 ms 11428 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 6128 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6116 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -