oj.uz

Submission #1074558

# Submission time Handle Problem Language Result Execution time Memory
1074558 2024-08-25T11:09:02 Z Elias Highway Tolls (IOI18_highway) C++17
12 / 100
 231 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 = 1;

	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 = 10000000;
		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
		{
			// assert(candidates[best].first == 0);
			assert(query_count <= 100);
			answer(root, candidates[best].first);
			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/02-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 0 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 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 344 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 85 ms 8804 KB Output is correct
4 Correct 88 ms 8796 KB Output is correct
5 Correct 89 ms 8808 KB Output is correct
6 Correct 71 ms 8868 KB Output is correct
7 Correct 72 ms 8848 KB Output is correct
8 Correct 77 ms 8760 KB Output is correct
9 Correct 70 ms 8688 KB Output is correct
10 Correct 77 ms 8732 KB Output is correct
11 Correct 81 ms 11272 KB Output is correct
12 Correct 96 ms 12888 KB Output is correct
13 Correct 74 ms 11624 KB Output is correct
14 Correct 69 ms 10336 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2708 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

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 214 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -