oj.uz

Submission #139129

# Submission time Handle Problem Language Result Execution time Memory
139129 2019-07-31T09:52:12 Z random0029 Highway Tolls (IOI18_highway) C++14
18 / 100
 413 ms 10216 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);
	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])
				Q[id] = 1;
		ll dd = ask(Q);
		if (dist == dd)
			le = md;
		else
		{
			for (int i = le; i < md; i ++)
				for (int id : Adj[i])
					Q[id] = 0;
			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 3156 KB Output is correct
2 Correct 4 ms 3152 KB Output is correct
3 Correct 4 ms 3064 KB Output is correct
4 Correct 5 ms 3064 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 4 ms 2984 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 4 ms 2984 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 4 ms 2984 KB Output is correct
11 Correct 6 ms 3108 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3132 KB Output is correct
2 Correct 40 ms 3668 KB Output is correct
3 Correct 189 ms 8584 KB Output is correct
4 Correct 303 ms 8576 KB Output is correct
5 Correct 222 ms 8588 KB Output is correct
6 Correct 200 ms 8608 KB Output is correct
7 Correct 248 ms 8536 KB Output is correct
8 Correct 269 ms 8608 KB Output is correct
9 Correct 220 ms 8536 KB Output is correct
10 Correct 257 ms 8592 KB Output is correct
11 Correct 331 ms 8476 KB Output is correct
12 Correct 300 ms 8368 KB Output is correct
13 Correct 413 ms 8380 KB Output is correct
14 Correct 352 ms 8372 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3660 KB Output is correct
2 Correct 73 ms 4244 KB Output is correct
3 Correct 90 ms 4828 KB Output is correct
4 Correct 203 ms 8368 KB Output is correct
5 Correct 147 ms 8356 KB Output is correct
6 Correct 131 ms 8368 KB Output is correct
7 Correct 226 ms 8384 KB Output is correct
8 Correct 240 ms 8360 KB Output is correct
9 Correct 170 ms 8376 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3124 KB Output is correct
2 Correct 34 ms 3660 KB Output is correct
3 Correct 155 ms 7444 KB Output is correct
4 Correct 208 ms 8852 KB Output is correct
5 Correct 225 ms 8520 KB Output is correct
6 Correct 228 ms 8640 KB Output is correct
7 Correct 337 ms 8524 KB Output is correct
8 Correct 269 ms 8508 KB Output is correct
9 Correct 185 ms 8936 KB Output is correct
10 Correct 212 ms 8592 KB Output is correct
11 Correct 324 ms 8384 KB Output is correct
12 Correct 229 ms 8408 KB Output is correct
13 Correct 312 ms 8392 KB Output is correct
14 Correct 275 ms 8376 KB Output is correct
15 Correct 241 ms 8528 KB Output is correct
16 Correct 246 ms 8536 KB Output is correct
17 Correct 353 ms 8392 KB Output is correct
18 Correct 294 ms 8364 KB Output is correct
19 Correct 229 ms 8504 KB Output is correct
20 Correct 277 ms 8376 KB Output is correct
21 Correct 179 ms 9944 KB Output is correct
22 Correct 256 ms 9488 KB Output is correct
23 Correct 241 ms 9504 KB Output is correct
24 Incorrect 388 ms 9484 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3660 KB Output is correct
2 Correct 50 ms 3732 KB Output is correct
3 Correct 280 ms 8976 KB Output is correct
4 Correct 241 ms 9496 KB Output is correct
5 Incorrect 328 ms 10216 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 20 ms 3636 KB Output is correct
2 Correct 30 ms 3740 KB Output is correct
3 Correct 245 ms 9076 KB Output is correct
4 Correct 290 ms 9396 KB Output is correct
5 Correct 352 ms 9380 KB Output is correct
6 Correct 347 ms 10208 KB Output is correct
7 Correct 245 ms 9216 KB Output is correct
8 Correct 282 ms 9024 KB Output is correct
9 Correct 274 ms 9180 KB Output is correct
10 Correct 293 ms 10152 KB Output is correct
11 Correct 350 ms 9984 KB Output is correct
12 Correct 320 ms 10100 KB Output is correct
13 Correct 224 ms 8672 KB Output is correct
14 Correct 234 ms 8760 KB Output is correct
15 Correct 208 ms 8660 KB Output is correct
16 Correct 243 ms 8904 KB Output is correct
17 Correct 261 ms 8828 KB Output is correct
18 Correct 230 ms 8996 KB Output is correct
19 Incorrect 312 ms 9740 KB Output is incorrect: {s, t} is wrong.
20 Halted 0 ms 0 KB -