Submission #651608

#	Time	Username	Problem	Language	Result	Execution time	Memory
651608		ymm	Highway Tolls (IOI18_highway)	C++17	51 / 100	339 ms	23544 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;
mt19937_64 rd(time(0));

ll ask_edge(vector<int> T)
{
	vector<int> vec(m, 1);
	for (int e : T) {
		vec[e] = 0;
	}
	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;
		int par = ((ask_ver(V, l, mid) - A*len) / (B - A)) & 1;
		if (par)
			r = mid;
		else
			l = mid;
	}
	return V[l];
}

bool vis[N];
bool bad[N];
void dfs(int v, vector<int> &vec)
{
	vis[v] = 1;
	for (auto [u, _] : adj0[v]) {
		if (bad[u])
			continue;
		vec.push_back(v);
		if (vis[u])
			continue;
		dfs(u, vec);
	}
}

void bfs(int rt, vector<int> &T)
{
	vector<int> vec = {rt};
	vis[rt] = 1;
	for (int i = 0; i < vec.size(); ++i) {
		int v = vec[i];
		for (auto [u, e] : adj0[v]) {
			if (bad[u] || vis[u])
				continue;
			T.push_back(e);
			vis[u] = 1;
			vec.push_back(u);
		}
	}
}

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});
	}
	vector<int> dard(m);
	iota(dard.begin(), dard.end(), 0);
	len = ask_edge(dard)/A;
	for (;;) {
		vector<int> T, rts;
		memset(vis, 0, sizeof(vis));
		Loop (v,0,n) {
			if (bad[v] || vis[v])
				continue;
			vector<int> vec;
			dfs(v, vec);
			if (vec.size())
				rts.push_back(vec[rd()%vec.size()]);
		}
		memset(vis, 0, sizeof(vis));
		for (int rt : rts)
			bfs(rt, T);
		if (ask_edge(T) == len*A) {
			for (auto e : T) {
				int v = _V[e], u = _U[e];
				adj1[v].push_back({u, e});
				adj1[u].push_back({v, e});
			}
			break;
		}
		for (int rt : rts)
			bad[rt] = 1;
	}
	vector<int> V;
	for (;;) {
		V.clear();
		Loop (i,0,n)
			if (rd()&1)
				V.push_back(i);
		int par = ((ask_ver(V) - A*len) / (B - A)) & 1;
		if (par)
			break;
	}
	int s = bin_search(V);
	V.resize(n);
	iota(V.begin(), V.end(), 0);
	V.erase(V.begin()+s);
	int t = bin_search(V);
	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, std::vector<int>&)':
highway.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  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: 0 / 18
• Subtask 6: 0 / 31