oj.uz

Submission #139130

# Submission time Handle Problem Language Result Execution time Memory
139130 2019-07-31T09:53:45 Z random0029 Highway Tolls (IOI18_highway) C++14
18 / 100
 422 ms 19704 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);
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				Q[id] = 0;
		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 3072 KB Output is correct
2 Correct 4 ms 3068 KB Output is correct
3 Correct 5 ms 2960 KB Output is correct
4 Correct 4 ms 3076 KB Output is correct
5 Correct 3 ms 3192 KB Output is correct
6 Correct 4 ms 3072 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 4 ms 3068 KB Output is correct
12 Correct 5 ms 3068 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 16 ms 3668 KB Output is correct
3 Correct 236 ms 8588 KB Output is correct
4 Correct 258 ms 8584 KB Output is correct
5 Correct 218 ms 8576 KB Output is correct
6 Correct 211 ms 8516 KB Output is correct
7 Correct 203 ms 8520 KB Output is correct
8 Correct 239 ms 8596 KB Output is correct
9 Correct 300 ms 8528 KB Output is correct
10 Correct 344 ms 8588 KB Output is correct
11 Correct 422 ms 8364 KB Output is correct
12 Correct 266 ms 8380 KB Output is correct
13 Correct 308 ms 8388 KB Output is correct
14 Correct 234 ms 8352 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3652 KB Output is correct
2 Correct 25 ms 4248 KB Output is correct
3 Correct 52 ms 4828 KB Output is correct
4 Correct 256 ms 8364 KB Output is correct
5 Correct 209 ms 8364 KB Output is correct
6 Correct 162 ms 8348 KB Output is correct
7 Correct 112 ms 8376 KB Output is correct
8 Correct 100 ms 8352 KB Output is correct
9 Correct 134 ms 8372 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3120 KB Output is correct
2 Correct 21 ms 3672 KB Output is correct
3 Correct 218 ms 7328 KB Output is correct
4 Correct 282 ms 8860 KB Output is correct
5 Correct 236 ms 8568 KB Output is correct
6 Correct 209 ms 8648 KB Output is correct
7 Correct 236 ms 8556 KB Output is correct
8 Correct 246 ms 8508 KB Output is correct
9 Correct 214 ms 8884 KB Output is correct
10 Correct 248 ms 8600 KB Output is correct
11 Correct 289 ms 8376 KB Output is correct
12 Correct 271 ms 8360 KB Output is correct
13 Correct 312 ms 8380 KB Output is correct
14 Correct 330 ms 8368 KB Output is correct
15 Correct 261 ms 8596 KB Output is correct
16 Correct 241 ms 8540 KB Output is correct
17 Correct 324 ms 8384 KB Output is correct
18 Correct 387 ms 8372 KB Output is correct
19 Correct 226 ms 8636 KB Output is correct
20 Correct 303 ms 8388 KB Output is correct
21 Correct 192 ms 9968 KB Output is correct
22 Correct 262 ms 9484 KB Output is correct
23 Correct 283 ms 9456 KB Output is correct
24 Incorrect 300 ms 9480 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3780 KB Output is correct
2 Correct 27 ms 3724 KB Output is correct
3 Correct 241 ms 8940 KB Output is correct
4 Correct 405 ms 9520 KB Output is correct
5 Runtime error 363 ms 19704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3708 KB Output is correct
2 Correct 27 ms 3752 KB Output is correct
3 Correct 267 ms 9076 KB Output is correct
4 Correct 251 ms 9432 KB Output is correct
5 Correct 300 ms 9412 KB Output is correct
6 Incorrect 300 ms 9980 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -