oj.uz

Submission #139134

# Submission time Handle Problem Language Result Execution time Memory
139134 2019-07-31T09:55:35 Z random0029 Highway Tolls (IOI18_highway) C++14
18 / 100
 393 ms 10292 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 5 ms 3112 KB Output is correct
2 Correct 4 ms 3068 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 4 ms 3060 KB Output is correct
6 Correct 5 ms 3080 KB Output is correct
7 Correct 4 ms 3076 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 4 ms 3064 KB Output is correct
10 Correct 5 ms 3056 KB Output is correct
11 Correct 4 ms 3156 KB Output is correct
12 Correct 4 ms 3072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 37 ms 3668 KB Output is correct
3 Correct 216 ms 8592 KB Output is correct
4 Correct 221 ms 8644 KB Output is correct
5 Correct 190 ms 8592 KB Output is correct
6 Correct 246 ms 8520 KB Output is correct
7 Correct 240 ms 8536 KB Output is correct
8 Correct 256 ms 8596 KB Output is correct
9 Correct 240 ms 8544 KB Output is correct
10 Correct 222 ms 8588 KB Output is correct
11 Correct 312 ms 8368 KB Output is correct
12 Correct 317 ms 8364 KB Output is correct
13 Correct 310 ms 8464 KB Output is correct
14 Correct 230 ms 8488 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3648 KB Output is correct
2 Correct 50 ms 4232 KB Output is correct
3 Correct 52 ms 4832 KB Output is correct
4 Correct 133 ms 8372 KB Output is correct
5 Correct 188 ms 8460 KB Output is correct
6 Correct 153 ms 8484 KB Output is correct
7 Correct 166 ms 8376 KB Output is correct
8 Correct 157 ms 8364 KB Output is correct
9 Correct 182 ms 8368 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3112 KB Output is correct
2 Correct 22 ms 3676 KB Output is correct
3 Correct 210 ms 7348 KB Output is correct
4 Correct 264 ms 8976 KB Output is correct
5 Correct 258 ms 8520 KB Output is correct
6 Correct 230 ms 8680 KB Output is correct
7 Correct 214 ms 8528 KB Output is correct
8 Correct 223 ms 8536 KB Output is correct
9 Correct 252 ms 9044 KB Output is correct
10 Correct 274 ms 8572 KB Output is correct
11 Correct 393 ms 8440 KB Output is correct
12 Correct 266 ms 8404 KB Output is correct
13 Correct 317 ms 8368 KB Output is correct
14 Correct 320 ms 8380 KB Output is correct
15 Correct 217 ms 8556 KB Output is correct
16 Correct 237 ms 8632 KB Output is correct
17 Correct 309 ms 8364 KB Output is correct
18 Correct 302 ms 8388 KB Output is correct
19 Correct 241 ms 8520 KB Output is correct
20 Correct 334 ms 8412 KB Output is correct
21 Correct 207 ms 9968 KB Output is correct
22 Correct 195 ms 9492 KB Output is correct
23 Correct 280 ms 9512 KB Output is correct
24 Incorrect 289 ms 9468 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 3704 KB Output is correct
2 Correct 31 ms 3736 KB Output is correct
3 Correct 273 ms 8972 KB Output is correct
4 Correct 283 ms 9512 KB Output is correct
5 Incorrect 334 ms 10292 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 23 ms 3732 KB Output is correct
2 Correct 30 ms 3736 KB Output is correct
3 Correct 267 ms 9064 KB Output is correct
4 Correct 308 ms 9412 KB Output is correct
5 Correct 289 ms 9416 KB Output is correct
6 Correct 328 ms 10208 KB Output is correct
7 Correct 280 ms 9244 KB Output is correct
8 Correct 304 ms 9016 KB Output is correct
9 Correct 290 ms 9184 KB Output is correct
10 Correct 323 ms 10148 KB Output is correct
11 Correct 330 ms 9988 KB Output is correct
12 Correct 320 ms 9992 KB Output is correct
13 Correct 238 ms 8780 KB Output is correct
14 Correct 236 ms 8732 KB Output is correct
15 Correct 224 ms 8664 KB Output is correct
16 Correct 239 ms 8900 KB Output is correct
17 Correct 253 ms 8828 KB Output is correct
18 Correct 198 ms 8884 KB Output is correct
19 Incorrect 288 ms 9740 KB Output is incorrect: {s, t} is wrong.
20 Halted 0 ms 0 KB -