Submission #651823

#	Time	Username	Problem	Language	Result	Execution time	Memory
651823		ymm	Highway Tolls (IOI18_highway)	C++17	100 / 100	465 ms	18552 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 150'010;
int len;
vector<pii> adj0[N];
vector<pii> adj1[N];
int n, m;
ll A, B;

ll ask_edge(bool def, vector<int> T)
{
	vector<int> vec(m, def);
	for (int e : T) {
		vec[e] = !def;
	}
	return ask(vec);
}

ll ask_ver(vector<int> V, int l, int r)
{
	vector<int> vec(m, 1);
	Loop (i,0,n)
		for (auto [_, e] : adj1[i])
			vec[e] = 0;
	Loop (i,l,r)
		for (auto [_, e] : adj1[V[i]])
			vec[e] = 1;
	return ask(vec);
}

ll ask_ver(vector<int> V) { return ask_ver(V, 0, V.size()); }

int bin_search(vector<int> V)
{
	int l = 0, r = V.size();
	while (r - l > 1) {
		int mid = (l+r)/2;
		ll dis = ask_ver(V, mid, V.size());
		if (dis == A*len)
			r = mid;
		else
			l = mid;
	}
	return V[l];
}

bool vis[N];
void bfs(int rt0, int rt1, vector<int> &vrt0, vector<int> &vrt1, vector<int> &T)
{
	vrt0 = {rt0}; vrt1 = {rt1};
	vector<int> *ans[2] = {&vrt0, &vrt1};
	vector<pii> vec = {{rt0,0},{rt1,1}};
	vis[rt0] = vis[rt1] = 1;
	for (int i = 0; i < vec.size(); ++i) {
		auto [v, c] = vec[i];
		for (auto [u, e] : adj0[v]) {
			if (vis[u])
				continue;
			vis[u] = 1;
			ans[c]->push_back(u);
			vec.push_back({u,c});
			T.push_back(e);
		}
	}
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B)
{
	n = _N; m = _U.size(); A = _A; B = _B;
	Loop (e,0,m) {
		int v = _V[e], u = _U[e];
		adj0[v].push_back({u, e});
		adj0[u].push_back({v, e});
	}
	len = ask_edge(0, {})/A;
	vector<int> V1, V2;
	{
		int l = 0, r = m;
		while (r - l > 1) {
			int mid = (l+r)/2;
			vector<int> vec(mid);
			iota(vec.begin(), vec.end(), 0);
			if (ask_edge(0, vec) != len*A)
				r = mid;
			else
				l = mid;
		}
		vector<int> T = {l};
		bfs(_U[l], _V[l], V1, V2, T);
		for (int e : T) {
			int v = _V[e], u = _U[e];
			adj1[v].push_back({u, e});
			adj1[u].push_back({v, e});
		}
	}
	int s = bin_search(V1);
	int t = bin_search(V2);
	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
highway.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < vec.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

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