Submission #295325

#	Time	Username	Problem	Language	Result	Execution time	Memory
295325		SeDunion	Highway Tolls (IOI18_highway)	C++17	0 / 100	27 ms	15360 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int M;
ll nask (vector<int> v) {
	vector<int> w(M, 0);
	for (int i : v) w[i] = 1;
	return ask (w);
}
ll rask (vector<int> v) {
	vector<int> w(M, 1);
	for (int i : v) w[i] = 0;
	return ask (w);
}
const int MAXN = 2e5;
vector<pair<int,int>> g[MAXN], mb, h[2][MAXN];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[U[i]].push_back ({V[i], i});
		g[V[i]].push_back ({U[i], i});
	}
	ll dist = nask ({}) / A;
	int l = 0, r = M - 1;
	while (l < r) {
		int m = (l + r) >> 1;
		vector<int> now;
		for (int i = l ; i <= m ; ++ i) {
			now.push_back (i);
		}
		if (rask (now) < dist * B) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	int u = U[r], v = V[r];
	int ei = r;
	assert (rask({r}) < dist*B);
	vector<int>from(N,-1);
	vector<int>id(N,-1);
	vector<int>d(N,MAXN);
	queue<int>q;
	q.push(u),q.push(v);
	d[u] = d[v] = 0;
	from[u] = 0;
	from[v] = 1;
	while(q.size()) {
		int v = q.front(); q.pop();
		for (auto [to, i] : g[v]) if (d[to] > d[v] + 1) {
			from[to] = from[v];
			d[to] = d[v] + 1;
			q.push(to);
			id[to] = i;
		}
	}
	for (int i = 0 ; i < N ; ++ i) {
		// cerr<<from[i] << " " << d[i] <<" from d\n";
		h[from[i]][d[i]].push_back ({i, id[i]});
	}
	vector<int>ans(2,-1);
	// cout << u << " <-> " << v << "\n";
	for (int i = 0 ; i < 2 ; ++ i) {
		vector<pair<int,int>>now;
		for(int F = 0 ; F <= N ; ++ F) {
			for (auto p : h[i][F]) now.push_back (p);
		}
		// for(auto p : now)cout<<p.first<<" ";
		// cout<<"\n";
		assert (now.size());
		int l = 0, r = now.size() - 1;
		// int ans = 0;
		while (l < r) {
			int m = (l + r + 1) >> 1;
			vector<int>cur={ei};
			cout<<l<<" "<<r<<" []\n";
			for(int ia = m;  ia <= r ; ++ ia) {
				cur.push_back(now[ia].second);
			}
			if(rask(cur)==dist*B-B+A) {
				// ans = m - 1;
				r = m - 1;
			} else {
				l = m;
			}
		}
		ans[i] = now[l].first;
	}
	// cout<<ans[0] << " " << ans[1] << " www\n";
	answer (ans[0], ans[1]);
}

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