Submission #1074592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074592		Elias	Highway Tolls (IOI18_highway)	C++17	51 / 100	282 ms	262144 KiB

highway

#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 (stderr)

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31