oj.uz

Submission #139109

# Submission time Handle Problem Language Result Execution time Memory
139109 2019-07-31T09:32:54 Z Mahdi_Jfri Highway Tolls (IOI18_highway) C++14
51 / 100
 253 ms 11948 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];

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5416 KB Output is correct
2 Correct 6 ms 5420 KB Output is correct
3 Correct 7 ms 5372 KB Output is correct
4 Correct 8 ms 5528 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 7 ms 5416 KB Output is correct
8 Correct 7 ms 5368 KB Output is correct
9 Correct 7 ms 5368 KB Output is correct
10 Correct 7 ms 5416 KB Output is correct
11 Correct 6 ms 5416 KB Output is correct
12 Correct 7 ms 5496 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5416 KB Output is correct
2 Correct 29 ms 6008 KB Output is correct
3 Correct 212 ms 11544 KB Output is correct
4 Correct 208 ms 11528 KB Output is correct
5 Correct 198 ms 11612 KB Output is correct
6 Correct 197 ms 11540 KB Output is correct
7 Correct 201 ms 11632 KB Output is correct
8 Correct 219 ms 11532 KB Output is correct
9 Correct 195 ms 11560 KB Output is correct
10 Correct 217 ms 11652 KB Output is correct
11 Correct 165 ms 11452 KB Output is correct
12 Correct 209 ms 11452 KB Output is correct
13 Correct 210 ms 11532 KB Output is correct
14 Correct 216 ms 11424 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6096 KB Output is correct
2 Correct 42 ms 6788 KB Output is correct
3 Correct 75 ms 7432 KB Output is correct
4 Correct 178 ms 11428 KB Output is correct
5 Correct 186 ms 11448 KB Output is correct
6 Correct 175 ms 11448 KB Output is correct
7 Correct 195 ms 11440 KB Output is correct
8 Correct 169 ms 11424 KB Output is correct
9 Correct 196 ms 11448 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5480 KB Output is correct
2 Correct 38 ms 6176 KB Output is correct
3 Correct 167 ms 10272 KB Output is correct
4 Correct 217 ms 11580 KB Output is correct
5 Correct 214 ms 11532 KB Output is correct
6 Correct 209 ms 11644 KB Output is correct
7 Correct 229 ms 11524 KB Output is correct
8 Correct 253 ms 11580 KB Output is correct
9 Correct 207 ms 11536 KB Output is correct
10 Correct 214 ms 11604 KB Output is correct
11 Correct 202 ms 11532 KB Output is correct
12 Correct 206 ms 11436 KB Output is correct
13 Correct 203 ms 11424 KB Output is correct
14 Correct 218 ms 11428 KB Output is correct
15 Correct 208 ms 11664 KB Output is correct
16 Correct 221 ms 11540 KB Output is correct
17 Correct 211 ms 11436 KB Output is correct
18 Correct 190 ms 11448 KB Output is correct
19 Correct 204 ms 11536 KB Output is correct
20 Correct 201 ms 11564 KB Output is correct
21 Correct 190 ms 11792 KB Output is correct
22 Correct 199 ms 11948 KB Output is correct
23 Correct 208 ms 11884 KB Output is correct
24 Correct 194 ms 11848 KB Output is correct
25 Correct 202 ms 11512 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 6132 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 30 ms 6124 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -