oj.uz

Submission #1074462

# Submission time Handle Problem Language Result Execution time Memory
1074462 2024-08-25T10:37:36 Z Elias Highway Tolls (IOI18_highway) C++17
11 / 100
 192 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;

	while (true)
	{
		ll initial = ask(vector<int>(U.size(), 0));

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

		int low = 0;
		int high = N;
		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;
			}
		}

		assert(best != 0);

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

		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;
			}
		}

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

#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()
{
	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:59: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]
   59 |    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 1 ms 344 KB Output is correct
6 Correct 1 ms 344 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 83 ms 8976 KB Output is correct
4 Incorrect 87 ms 8792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2728 KB Output is correct
2 Correct 18 ms 5212 KB Output is correct
3 Correct 26 ms 7496 KB Output is correct
4 Correct 74 ms 21920 KB Output is correct
5 Correct 92 ms 21932 KB Output is correct
6 Correct 83 ms 22736 KB Output is correct
7 Correct 77 ms 23012 KB Output is correct
8 Correct 78 ms 22600 KB Output is correct
9 Correct 80 ms 24216 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1428 KB Output is correct
3 Correct 59 ms 6840 KB Output is correct
4 Correct 87 ms 8664 KB Output is correct
5 Correct 73 ms 9072 KB Output is correct
6 Correct 78 ms 8756 KB Output is correct
7 Correct 75 ms 8764 KB Output is correct
8 Correct 79 ms 8944 KB Output is correct
9 Incorrect 96 ms 8852 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 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 184 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -