Submission #96702

#	Time	Username	Problem	Language	Result	Execution time	Memory
96702		diamond_duke	Highway Tolls (IOI18_highway)	C++11	100 / 100	352 ms	10584 KiB

highway

#include "highway.h"
void find_pair(int n, std::vector<int> eu, std::vector<int> ev, int, int)
{
	auto dis = ask(std::vector<int>(eu.size()));
	auto find_edge = [&]
	{
		int l = 0, r = (int)eu.size() - 1, res = -1;
		while (l <= r)
		{
			int m = l + r >> 1;
			std::vector<int> vec(eu.size());
			for (int i = 0; i <= m; i++)
				vec[i] = 1;
			if (ask(vec) > dis)
			{
				res = m;
				r = m - 1;
			}
			else
				l = m + 1;
		}
		return res;
	};
	std::vector<std::vector<int> > adj(n);
	for (int i = 0; i < eu.size(); i++)
	{
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	int e_sp = find_edge();
	std::vector<int> vec_l = {eu[e_sp]}, vec_r = {ev[e_sp]};
	std::vector<int> bel(n, -1), tree = {e_sp}, que = {eu[e_sp], ev[e_sp]};
	bel[eu[e_sp]] = 0;
	bel[ev[e_sp]] = 1;
	for (int he = 0; he < que.size(); he++)
	{
		int u = que[he];
		for (int e : adj[u])
		{
			int v = eu[e] ^ ev[e] ^ u;
			if (~bel[v])
				continue;
			tree.push_back(e);
			que.push_back(v);
			bel[v] = bel[u];
			(bel[v] ? vec_r : vec_l).push_back(v);
		}
	}
	auto solve = [&] (std::vector<int> &node)
	{
		std::vector<int> idx(n, -1);
		for (int i = 0; i < node.size(); i++)
			idx[node[i]] = i;
		int l = 0, r = (int)node.size() - 1, res = -1;
		while (l <= r)
		{
			int m = l + r >> 1;
			std::vector<int> vec(eu.size(), 1);
			for (int e : tree)
				vec[e] = idx[eu[e]] >= m || idx[ev[e]] >= m;
			if (ask(vec) == dis)
				r = m - 1;
			else
			{
				res = m;
				l = m + 1;
			}
		}
		return node[res];
	};
	answer(solve(vec_l), solve(vec_r));
}

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:10:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < eu.size(); i++)
                  ~~^~~~~~~~~~~
highway.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int he = 0; he < que.size(); he++)
                   ~~~^~~~~~~~~~~~
highway.cpp: In lambda function:
highway.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < node.size(); i++)
                   ~~^~~~~~~~~~~~~
highway.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31