oj.uz

Submission #139117

# Submission time Handle Problem Language Result Execution time Memory
139117 2019-07-31T09:39:04 Z Mahdi_Jfri Highway Tolls (IOI18_highway) C++14
69 / 100
 308 ms 12820 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] , m , n;

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++)
	{
		if(m == n - 1)
			tw[i] = (is[from[i]] != is[to[i]]);
		else
			tw[i] = (is[from[i]] == is[to[i]]);
	}

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

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

	n = N , 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;
	}

	if(m == n - 1)
		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 5368 KB Output is correct
2 Correct 7 ms 5424 KB Output is correct
3 Correct 6 ms 5416 KB Output is correct
4 Correct 7 ms 5420 KB Output is correct
5 Correct 7 ms 5392 KB Output is correct
6 Correct 7 ms 5416 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5416 KB Output is correct
9 Correct 7 ms 5364 KB Output is correct
10 Correct 8 ms 5372 KB Output is correct
11 Correct 8 ms 5420 KB Output is correct
12 Correct 7 ms 5416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5424 KB Output is correct
2 Correct 28 ms 6008 KB Output is correct
3 Correct 201 ms 11532 KB Output is correct
4 Correct 217 ms 11528 KB Output is correct
5 Correct 195 ms 11532 KB Output is correct
6 Correct 218 ms 11544 KB Output is correct
7 Correct 211 ms 11560 KB Output is correct
8 Correct 219 ms 11548 KB Output is correct
9 Correct 197 ms 11540 KB Output is correct
10 Correct 191 ms 11568 KB Output is correct
11 Correct 216 ms 11424 KB Output is correct
12 Correct 190 ms 11536 KB Output is correct
13 Correct 215 ms 11440 KB Output is correct
14 Correct 209 ms 11436 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6124 KB Output is correct
2 Correct 42 ms 6796 KB Output is correct
3 Correct 66 ms 7408 KB Output is correct
4 Correct 155 ms 11444 KB Output is correct
5 Correct 153 ms 11488 KB Output is correct
6 Correct 191 ms 11440 KB Output is correct
7 Correct 174 ms 11536 KB Output is correct
8 Correct 156 ms 11440 KB Output is correct
9 Correct 160 ms 11444 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 28 ms 6008 KB Output is correct
3 Correct 168 ms 10264 KB Output is correct
4 Correct 217 ms 11708 KB Output is correct
5 Correct 215 ms 11532 KB Output is correct
6 Correct 201 ms 11520 KB Output is correct
7 Correct 202 ms 11520 KB Output is correct
8 Correct 200 ms 11808 KB Output is correct
9 Correct 218 ms 11596 KB Output is correct
10 Correct 214 ms 11528 KB Output is correct
11 Correct 214 ms 11428 KB Output is correct
12 Correct 225 ms 11452 KB Output is correct
13 Correct 219 ms 11544 KB Output is correct
14 Correct 201 ms 11544 KB Output is correct
15 Correct 209 ms 11540 KB Output is correct
16 Correct 209 ms 11536 KB Output is correct
17 Correct 230 ms 11432 KB Output is correct
18 Correct 219 ms 11448 KB Output is correct
19 Correct 193 ms 11544 KB Output is correct
20 Correct 218 ms 11452 KB Output is correct
21 Correct 202 ms 11840 KB Output is correct
22 Correct 185 ms 11796 KB Output is correct
23 Correct 195 ms 11804 KB Output is correct
24 Correct 194 ms 11780 KB Output is correct
25 Correct 209 ms 11492 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6008 KB Output is correct
2 Correct 32 ms 6164 KB Output is correct
3 Correct 239 ms 11756 KB Output is correct
4 Correct 260 ms 12156 KB Output is correct
5 Correct 303 ms 12820 KB Output is correct
6 Correct 291 ms 12808 KB Output is correct
7 Correct 294 ms 12812 KB Output is correct
8 Correct 307 ms 12816 KB Output is correct
9 Correct 255 ms 10908 KB Output is correct
10 Correct 267 ms 11320 KB Output is correct
11 Correct 263 ms 11324 KB Output is correct
12 Correct 292 ms 12436 KB Output is correct
13 Correct 306 ms 12536 KB Output is correct
14 Correct 308 ms 12696 KB Output is correct
15 Correct 294 ms 12684 KB Output is correct
16 Correct 282 ms 11620 KB Output is correct
17 Correct 204 ms 11884 KB Output is correct
18 Correct 209 ms 11948 KB Output is correct
19 Correct 195 ms 11896 KB Output is correct
20 Correct 191 ms 11992 KB Output is correct
21 Correct 299 ms 12760 KB Output is correct

Subtask #6
0 / 31.0

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