oj.uz

Submission #139142

# Submission time Handle Problem Language Result Execution time Memory
139142 2019-07-31T10:00:20 Z random0029 Highway Tolls (IOI18_highway) C++14
18 / 100
 347 ms 10732 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;
	{
		for (int id : Adj[root])
			Q[id] = 1;
		ll dd = ask(Q);
		if (dd == dist)
			assert(0);
	}
	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 3064 KB Output is correct
2 Correct 4 ms 2984 KB Output is correct
3 Correct 4 ms 2984 KB Output is correct
4 Correct 5 ms 3064 KB Output is correct
5 Correct 4 ms 2984 KB Output is correct
6 Correct 4 ms 2984 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct
9 Correct 5 ms 3080 KB Output is correct
10 Correct 4 ms 3068 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct
12 Correct 4 ms 3148 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3108 KB Output is correct
2 Correct 26 ms 3624 KB Output is correct
3 Correct 270 ms 9000 KB Output is correct
4 Correct 242 ms 8936 KB Output is correct
5 Correct 222 ms 8936 KB Output is correct
6 Correct 288 ms 8864 KB Output is correct
7 Correct 204 ms 8868 KB Output is correct
8 Correct 253 ms 8944 KB Output is correct
9 Correct 247 ms 8872 KB Output is correct
10 Correct 223 ms 8932 KB Output is correct
11 Correct 328 ms 8732 KB Output is correct
12 Correct 330 ms 8724 KB Output is correct
13 Correct 314 ms 8720 KB Output is correct
14 Correct 256 ms 8736 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3696 KB Output is correct
2 Correct 37 ms 4324 KB Output is correct
3 Correct 38 ms 4944 KB Output is correct
4 Correct 122 ms 8728 KB Output is correct
5 Correct 194 ms 8740 KB Output is correct
6 Correct 161 ms 8720 KB Output is correct
7 Correct 150 ms 8736 KB Output is correct
8 Correct 165 ms 8840 KB Output is correct
9 Correct 236 ms 8716 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3112 KB Output is correct
2 Correct 33 ms 3696 KB Output is correct
3 Correct 141 ms 7624 KB Output is correct
4 Correct 253 ms 9208 KB Output is correct
5 Correct 315 ms 8848 KB Output is correct
6 Correct 263 ms 8964 KB Output is correct
7 Correct 245 ms 8900 KB Output is correct
8 Correct 234 ms 8864 KB Output is correct
9 Correct 212 ms 9292 KB Output is correct
10 Correct 217 ms 8956 KB Output is correct
11 Correct 270 ms 8808 KB Output is correct
12 Correct 275 ms 8748 KB Output is correct
13 Correct 308 ms 8840 KB Output is correct
14 Correct 323 ms 8740 KB Output is correct
15 Correct 246 ms 8944 KB Output is correct
16 Correct 247 ms 8888 KB Output is correct
17 Correct 345 ms 8752 KB Output is correct
18 Correct 318 ms 8724 KB Output is correct
19 Correct 246 ms 8888 KB Output is correct
20 Correct 341 ms 8780 KB Output is correct
21 Correct 223 ms 10332 KB Output is correct
22 Correct 215 ms 9812 KB Output is correct
23 Incorrect 310 ms 9868 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3752 KB Output is correct
2 Correct 30 ms 3796 KB Output is correct
3 Correct 264 ms 9348 KB Output is correct
4 Correct 290 ms 9940 KB Output is correct
5 Incorrect 327 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 33 ms 3832 KB Output is correct
2 Correct 27 ms 3816 KB Output is correct
3 Correct 262 ms 9432 KB Output is correct
4 Correct 275 ms 9812 KB Output is correct
5 Correct 304 ms 9952 KB Output is correct
6 Correct 314 ms 10708 KB Output is correct
7 Correct 273 ms 9624 KB Output is correct
8 Correct 256 ms 9488 KB Output is correct
9 Correct 285 ms 9608 KB Output is correct
10 Correct 330 ms 10732 KB Output is correct
11 Correct 336 ms 10496 KB Output is correct
12 Correct 347 ms 10516 KB Output is correct
13 Correct 245 ms 9172 KB Output is correct
14 Correct 249 ms 9280 KB Output is correct
15 Correct 243 ms 9168 KB Output is correct
16 Correct 259 ms 9432 KB Output is correct
17 Correct 257 ms 9404 KB Output is correct
18 Correct 234 ms 9404 KB Output is correct
19 Incorrect 326 ms 10248 KB Output is incorrect: {s, t} is wrong.
20 Halted 0 ms 0 KB -