oj.uz

답안 #1074542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074542 2024-08-25T11:03:52 Z Elias 통행료 (IOI18_highway) C++17
12 / 100
 222 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-04.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 340 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 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 0 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 74 ms 8972 KB Output is correct
4 Correct 71 ms 8792 KB Output is correct
5 Correct 72 ms 8796 KB Output is correct
6 Correct 76 ms 8668 KB Output is correct
7 Correct 71 ms 8868 KB Output is correct
8 Correct 69 ms 8704 KB Output is correct
9 Correct 69 ms 8704 KB Output is correct
10 Correct 73 ms 8736 KB Output is correct
11 Correct 76 ms 11276 KB Output is correct
12 Correct 92 ms 12760 KB Output is correct
13 Correct 86 ms 11640 KB Output is correct
14 Correct 73 ms 10588 KB Output is correct

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 2708 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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