oj.uz

Submission #1074592

# Submission time Handle Problem Language Result Execution time Memory
1074592 2024-08-25T11:20:23 Z Elias Highway Tolls (IOI18_highway) C++17
51 / 100
 282 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
long long ask(const std::vector<int> &w);
void answer(int s, int t);
#else
#include "highway.h"
#endif

vector<vector<pair<int, int>>> adj;

void get_depth(int i, int ri, vector<vector<pair<int, int>>> &with, int d = 0, int p = -1)
{
	while (with.size() <= d)
		with.push_back({});
	with[d].push_back({i, ri});

	for (auto [c, ri] : adj[i])
	{
		if (c != p)
			get_depth(c, ri, with, d + 1, i);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
	adj.clear();
	adj.resize(N);
	int M = U.size();
	for (int i = 0; i < U.size(); i++)
	{
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}

	int root = 0;
	int tries = 0;

	ll initial = ask(vector<int>(M, 0));

	int query_count = 1;

	while (true)
	{
		vector<vector<pair<int, int>>> with_root;
		get_depth(root, -1, with_root);

		int low = 0;
		int high = with_root.size();
		int best = 0;

		while (low <= high)
		{
			int mid = (low + high) / 2;

			vector<int> query(M);
			for (int d = mid; d < with_root.size(); d++)
			{
				if (d == 0)
					continue;
				for (auto [i, ri] : with_root[d])
				{
					query[ri] = 1;
				}
			}

			if (ask(query) > initial)
			{
				best = mid;
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
			query_count++;
		}

		assert(best != 0);

		vector<pair<int, int>> candidates = with_root[best];

		assert(candidates.size());

		low = 0;
		high = candidates.size() - 1;
		best = candidates.size() - 1;

		while (low <= high)
		{
			int mid = (low + high) / 2;

			vector<int> query(M);
			for (int d = 0; d <= mid; d++)
			{
				query[candidates[d].second] = 1;
			}

			if (ask(query) > initial)
			{
				best = mid;
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
			query_count++;
		}

		if (tries == 0)
		{
			root = candidates[best].first;
			tries++;
		}
		else
		{
			answer(candidates[best].first, root);
			break;
		}
	}
}

#ifdef _DEBUG

namespace
{

	constexpr int MAX_NUM_CALLS = 100;
	constexpr long long INF = 1LL << 61;

	int N, M, A, B, S, T;
	std::vector<int> U, V;
	std::vector<std::vector<std::pair<int, int>>> graph;

	bool answered, wrong_pair;
	int num_calls;

	int read_int()
	{
		int x;
		if (scanf("%d", &x) != 1)
		{
			fprintf(stderr, "Error while reading input\n");
			exit(1);
		}
		return x;
	}

	void wrong_answer(const char *MSG)
	{
		printf("Wrong Answer: %s\n", MSG);
		exit(0);
	}

} // namespace

long long ask(const std::vector<int> &w)
{
	if (++num_calls > MAX_NUM_CALLS)
	{
		wrong_answer("more than 100 calls to ask");
	}
	if (w.size() != (size_t)M)
	{
		wrong_answer("w is invalid");
	}
	for (size_t i = 0; i < w.size(); ++i)
	{
		if (!(w[i] == 0 || w[i] == 1))
		{
			wrong_answer("w is invalid");
		}
	}

	std::vector<bool> visited(N, false);
	std::vector<long long> current_dist(N, INF);
	std::queue<int> qa, qb;
	qa.push(S);
	current_dist[S] = 0;
	while (!qa.empty() || !qb.empty())
	{
		int v;
		if (qb.empty() ||
			(!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()]))
		{
			v = qa.front();
			qa.pop();
		}
		else
		{
			v = qb.front();
			qb.pop();
		}
		if (visited[v])
		{
			continue;
		}
		visited[v] = true;
		long long d = current_dist[v];
		if (v == T)
		{
			return d;
		}
		for (auto e : graph[v])
		{
			int vv = e.first;
			int ei = e.second;
			if (!visited[vv])
			{
				if (w[ei] == 0)
				{
					if (current_dist[vv] > d + A)
					{
						current_dist[vv] = d + A;
						qa.push(vv);
					}
				}
				else
				{
					if (current_dist[vv] > d + B)
					{
						current_dist[vv] = d + B;
						qb.push(vv);
					}
				}
			}
		}
	}
	return -1;
}

void answer(int s, int t)
{
	if (answered)
	{
		wrong_answer("answered not exactly once");
	}

	if (!((s == S && t == T) || (s == T && t == S)))
	{
		wrong_pair = true;
	}

	answered = true;
}

int main()
{
	freopen("/home/elias/Downloads/ioi2018tests/highway/in/04-01.txt", "r", stdin);

	N = read_int();
	M = read_int();
	A = read_int();
	B = read_int();
	S = read_int();
	T = read_int();
	U.resize(M);
	V.resize(M);
	graph.assign(N, std::vector<std::pair<int, int>>());
	for (int i = 0; i < M; ++i)
	{
		U[i] = read_int();
		V[i] = read_int();
		graph[U[i]].push_back({V[i], i});
		graph[V[i]].push_back({U[i], i});
	}

	for (int s = 0; s < N; s++)
		for (int t = s + 1; t < N; t++)
		{
			S = s;
			T = t;
			answered = false;
			wrong_pair = false;
			num_calls = 0;
			find_pair(N, U, V, A, B);
			if (!answered)
			{
				wrong_answer("answered not exactly once");
			}
			if (wrong_pair)
			{
				wrong_answer("{s, t} is wrong");
			}
			printf("Accepted: %d\n", num_calls);
		}
	return 0;
}

#endif

Compilation message

highway.cpp: In function 'void get_depth(int, int, std::vector<std::vector<std::pair<int, int> > >&, int, int)':
highway.cpp:18:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |  while (with.size() <= d)
      |         ~~~~~~~~~~~~^~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < U.size(); i++)
      |                  ~~^~~~~~~~~~
highway.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for (int d = mid; d < with_root.size(); d++)
      |                      ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 7 ms 1276 KB Output is correct
3 Correct 86 ms 8852 KB Output is correct
4 Correct 79 ms 8800 KB Output is correct
5 Correct 77 ms 8808 KB Output is correct
6 Correct 76 ms 8792 KB Output is correct
7 Correct 75 ms 8860 KB Output is correct
8 Correct 82 ms 8720 KB Output is correct
9 Correct 79 ms 8800 KB Output is correct
10 Correct 80 ms 8756 KB Output is correct
11 Correct 94 ms 11436 KB Output is correct
12 Correct 104 ms 14056 KB Output is correct
13 Correct 97 ms 12048 KB Output is correct
14 Correct 88 ms 12280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2728 KB Output is correct
2 Correct 17 ms 5164 KB Output is correct
3 Correct 26 ms 7496 KB Output is correct
4 Correct 95 ms 21864 KB Output is correct
5 Correct 81 ms 21932 KB Output is correct
6 Correct 90 ms 23956 KB Output is correct
7 Correct 84 ms 23012 KB Output is correct
8 Correct 80 ms 22372 KB Output is correct
9 Correct 80 ms 23332 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1368 KB Output is correct
3 Correct 69 ms 6832 KB Output is correct
4 Correct 84 ms 8680 KB Output is correct
5 Correct 79 ms 8864 KB Output is correct
6 Correct 83 ms 8764 KB Output is correct
7 Correct 79 ms 8720 KB Output is correct
8 Correct 73 ms 8788 KB Output is correct
9 Correct 86 ms 8848 KB Output is correct
10 Correct 92 ms 8844 KB Output is correct
11 Correct 90 ms 11016 KB Output is correct
12 Correct 95 ms 13148 KB Output is correct
13 Correct 104 ms 12260 KB Output is correct
14 Correct 106 ms 13164 KB Output is correct
15 Correct 78 ms 8764 KB Output is correct
16 Correct 68 ms 8736 KB Output is correct
17 Correct 101 ms 12472 KB Output is correct
18 Correct 98 ms 12504 KB Output is correct
19 Correct 76 ms 8920 KB Output is correct
20 Correct 102 ms 14168 KB Output is correct
21 Correct 103 ms 9652 KB Output is correct
22 Correct 93 ms 9876 KB Output is correct
23 Correct 93 ms 9260 KB Output is correct
24 Correct 95 ms 10824 KB Output is correct
25 Correct 117 ms 22772 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 231 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 282 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -