oj.uz

Submission #139143

# Submission time Handle Problem Language Result Execution time Memory
139143 2019-07-31T10:01:08 Z random0029 Highway Tolls (IOI18_highway) C++14
18 / 100
 378 ms 10720 KB 
// ItnoE
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = N * 2;
int n, m, ts, X, Y, H[N], Mark[N], V[MXN], U[MXN];
ll ndist, dist;
vector < int > Q, Adj[N];
inline void BFS(int root)
{
	memset(H, -1, sizeof(H));
	H[root] = 0;
	queue < int > qu;
	qu.push(root);
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		for (int id : Adj[v])
		{
			int u = V[id] ^ U[id] ^ v;
			if (H[u] == -1)
				H[u] = H[v] + 1, qu.push(u);
		}
	}
}
inline int GetHeight()
{
	int Mxh = 0;
	for (int i = 0; i < n; i ++)
		Mxh = max(Mxh, H[i]);
	int le = 1, ri = Mxh + 1, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = 0; i < n; i ++)
			if (H[i] >= md)
				for (int id : Adj[i])
				{
					int u = V[id] ^ U[id] ^ i;
					if (H[u] < H[i])
						Q[id] = 1;
				}
		ll dd = ask(Q);
		if (dd == dist)
			ri = md;
		else
			le = md;
	}
	return (le);
}
inline int FindS(int h)
{
	ts ++;
	vector < int > vec;
	for (int i = 0; i < n; i ++)
		if (H[i] == h && (ts == 1 || Mark[i] == 1))
			vec.push_back(i);
	int le = 0, ri = (int)vec.size(), md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = le; i < md; i ++)
			for (int id : Adj[vec[i]])
			{
				int u = V[id] ^ U[id] ^ vec[i];
				if (H[u] < H[vec[i]])
					Q[id] = 1;
			}
		ll dd = ask(Q);
		if (dd == dist)
			le = md;
		else
			ri = md;
	}
	return (vec[le]);
}
void find_pair(int _n, vector < int > _V, vector < int > _U, int _X, int _Y)
{
	n = _n;
	m = (int)_V.size();
	X = _X; Y = _Y;
	for (int i = 0; i < m; i ++)
	{
		V[i] = _V[i]; U[i] = _U[i];
		Adj[V[i]].push_back(i);
		Adj[U[i]].push_back(i);
	}
	Q = vector < int > (m, 0);
	vector < int > QQ(m, 0);
	dist = ask(Q);
	ndist = dist / X;
	int le = 0, ri = n, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				QQ[id] ++;
		for (int i = 0; i < m; i ++)
			Q[i] = (QQ[i] > 0);
		ll dd = ask(Q);
		if (dist == dd)
			le = md;
		else
		{
			for (int i = le; i < md; i ++)
				for (int id : Adj[i])
					QQ[id] --;//aa
			ri = md;
		}
	}
	int root = le;
	BFS(root);
	int hs = GetHeight();
	int ht = ndist - hs;
	for (int i = 0; i < n; i ++)
		if (H[i] == ht)
			Mark[i] = 1;
	int s = FindS(hs);
	BFS(s);
	int t = FindS(ndist);
	answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 2984 KB Output is correct
3 Correct 4 ms 3192 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 5 ms 3080 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 3068 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 4 ms 3064 KB Output is correct
11 Correct 5 ms 2984 KB Output is correct
12 Correct 5 ms 3096 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3208 KB Output is correct
2 Correct 24 ms 3708 KB Output is correct
3 Correct 212 ms 8936 KB Output is correct
4 Correct 227 ms 8936 KB Output is correct
5 Correct 235 ms 8876 KB Output is correct
6 Correct 215 ms 8900 KB Output is correct
7 Correct 246 ms 8876 KB Output is correct
8 Correct 238 ms 8944 KB Output is correct
9 Correct 262 ms 8920 KB Output is correct
10 Correct 203 ms 8952 KB Output is correct
11 Correct 312 ms 8796 KB Output is correct
12 Correct 314 ms 8780 KB Output is correct
13 Correct 319 ms 8716 KB Output is correct
14 Correct 313 ms 8720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3772 KB Output is correct
2 Correct 45 ms 4392 KB Output is correct
3 Correct 73 ms 4996 KB Output is correct
4 Correct 187 ms 8724 KB Output is correct
5 Correct 160 ms 8824 KB Output is correct
6 Correct 174 ms 8736 KB Output is correct
7 Correct 183 ms 8736 KB Output is correct
8 Correct 183 ms 8716 KB Output is correct
9 Correct 175 ms 8720 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 28 ms 3752 KB Output is correct
3 Correct 171 ms 7560 KB Output is correct
4 Correct 240 ms 9180 KB Output is correct
5 Correct 251 ms 8876 KB Output is correct
6 Correct 252 ms 9164 KB Output is correct
7 Correct 241 ms 8876 KB Output is correct
8 Correct 239 ms 8860 KB Output is correct
9 Correct 240 ms 9228 KB Output is correct
10 Correct 246 ms 8940 KB Output is correct
11 Correct 271 ms 8808 KB Output is correct
12 Correct 281 ms 8804 KB Output is correct
13 Correct 319 ms 8800 KB Output is correct
14 Correct 332 ms 8732 KB Output is correct
15 Correct 241 ms 8876 KB Output is correct
16 Correct 226 ms 8892 KB Output is correct
17 Correct 319 ms 8748 KB Output is correct
18 Correct 318 ms 8724 KB Output is correct
19 Correct 231 ms 8876 KB Output is correct
20 Correct 315 ms 8744 KB Output is correct
21 Correct 197 ms 10332 KB Output is correct
22 Correct 206 ms 9780 KB Output is correct
23 Correct 281 ms 9880 KB Output is correct
24 Incorrect 310 ms 9796 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3744 KB Output is correct
2 Correct 29 ms 3788 KB Output is correct
3 Correct 287 ms 9344 KB Output is correct
4 Correct 296 ms 9940 KB Output is correct
5 Incorrect 378 ms 10720 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3732 KB Output is correct
2 Correct 40 ms 3804 KB Output is correct
3 Correct 251 ms 9476 KB Output is correct
4 Correct 289 ms 9812 KB Output is correct
5 Correct 302 ms 9844 KB Output is correct
6 Correct 344 ms 10716 KB Output is correct
7 Correct 277 ms 9636 KB Output is correct
8 Correct 293 ms 9416 KB Output is correct
9 Correct 301 ms 9616 KB Output is correct
10 Correct 333 ms 10636 KB Output is correct
11 Correct 305 ms 10476 KB Output is correct
12 Correct 329 ms 10488 KB Output is correct
13 Correct 256 ms 9164 KB Output is correct
14 Correct 214 ms 9272 KB Output is correct
15 Correct 175 ms 9164 KB Output is correct
16 Correct 220 ms 9432 KB Output is correct
17 Correct 265 ms 9376 KB Output is correct
18 Correct 217 ms 9468 KB Output is correct
19 Incorrect 298 ms 10380 KB Output is incorrect: {s, t} is wrong.
20 Halted 0 ms 0 KB -