oj.uz

답안 #1074579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074579 2024-08-25T11:16:49 Z Elias 통행료 (IOI18_highway) C++17
12 / 100
 213 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
		{
			assert(candidates[best].first == 0);
			assert(query_count <= 100);
			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/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

# 결과 실행 시간 메모리 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 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 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 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 87 ms 8840 KB Output is correct
4 Correct 80 ms 8788 KB Output is correct
5 Correct 78 ms 8808 KB Output is correct
6 Correct 78 ms 8772 KB Output is correct
7 Correct 70 ms 8872 KB Output is correct
8 Correct 77 ms 8760 KB Output is correct
9 Correct 76 ms 9008 KB Output is correct
10 Correct 79 ms 8768 KB Output is correct
11 Correct 92 ms 11432 KB Output is correct
12 Correct 98 ms 13580 KB Output is correct
13 Correct 91 ms 12044 KB Output is correct
14 Correct 95 ms 12036 KB Output is correct

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 5520 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 195 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 213 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -