Submission #762224

#	Time	Username	Problem	Language	Result	Execution time	Memory
762224		minhcool	Highway Tolls (IOI18_highway)	C++17	90 / 100	218 ms	19372 KiB

highway

//#define local
#ifndef local
#include "highway.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

// ask(vector<ll>)

vector<ii> Adj[N];

ll mini;

ll n, m;

vector<ii> v1, v2;

bool vis[N];

bool ck = 0;

vector<int> ok;

int dist;

/*
void dfs(ll u, ll d){
	vis[u] = 1;
	if(!ck) v1.pb({u, d});
	else v2.pb({u, d});
//	if(d == dist) ok.pb(u);
	for(auto it : Adj[u]){
		if(it.se < (mini - 1)) continue;
		if(vis[it.fi]) continue;
		dfs(it.fi, d + 1);
	}
}*/

bool cmp(ii a, ii b){
	return a.se > b.se;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N, m = U.size();
	for(ll i = 0; i < m; i++){
		Adj[U[i]].pb({V[i], i});
		Adj[V[i]].pb({U[i], i});
	}
	// first step: find the optimal ans by toggle all 0s
	ll opt;
	vector<int> temp;
	for(ll i = 0; i < m; i++) temp.pb(0);
	opt = ask(temp);
	// phase 1: let us set (1->i) to B in order to find a bridge + split graph llo two parts
	ll le = 0, ri = m - 1;
	while(le < ri){
		ll mid = (le + ri) >> 1;
		temp.clear();
		for(ll i = 0; i <= mid; i++) temp.pb(1);
		for(ll i = mid + 1; i < m; i++) temp.pb(0);
		ll get = ask(temp);
		if(get == opt) le = mid + 1;
		else ri = mid;
	}
	mini = le + 1;
	// phase 2: find S/T
	ck = 0;
	//dfs(U[le], 0);
	queue<int> q;
	vis[U[le]] = 1;
	q.push(U[le]);
	vector<int> distt(n + 1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
	//	if(distt[u] == dist) ok.pb(u);
		v1.pb({u, distt[u]});
		for(auto it : Adj[u]){
			int v = it.fi;
			if(it.se < (mini - 1)) continue;
			if(!vis[v]){
				vis[v] = 1;
				distt[v] = distt[u] + 1;
				q.push(v);
			}
		}
	}
	//ck = 1;
	//dfs(V[le], 0);
	sort(v1.begin(), v1.end(), cmp);
	//sort(v2.begin(), v2.end(), cmp);
	ll le2 = 0, ri2 = v1.size() - 1;
	while(le2 < ri2){
		ll mid = (le2 + ri2) >> 1;
		temp.resize(m);
		for(ll i = 0; i < le; i++) temp[i] = 1;
		temp[le] = 0;
		for(ll i = le + 1; i < m; i++) temp[i] = 0;
		for(ll i = 0; i <= mid; i++){
			ll u = v1[i].fi;
			for(auto it : Adj[u]){
				if(it.se < mini) continue;
				temp[it.se] = 1;
			}
		}
		ll get = ask(temp);
		if(get == opt) le2 = mid + 1;
		else ri2 = mid;
	}
	/*
	ll le3 = 0, ri3 = v2.size() - 1;
	while(le3 < ri3){
		ll mid = (le3 + ri3) >> 1;
		temp.resize(m);
		for(ll i = 0; i < le; i++) temp[i] = 1;
		temp[le] = 0;
		for(ll i = le + 1; i < m; i++) temp[i] = 0;
		for(ll i = 0; i <= mid; i++){
			ll u = v2[i].fi;
			for(auto it : Adj[u]){
				if(it.se < mini) continue;
				temp[it.se] = 1;
			}
		}
		ll get = ask(temp);
		if(get == opt) le3 = mid + 1;
		else ri3 = mid;
	}*/
	int S = v1[(int)le2].fi;
	dist = opt / A;
//	cout << S << " " << opt << " " << A << " " << dist << "\n";
	ok.clear();
	mini = 0;
	for(int i = 0; i < n; i++) vis[i] = 0;
	for(int i = 0; i <= n; i++) distt[i] = 0;
	vis[S] = 1;
	q.push(S);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(distt[u] == dist) ok.pb(u);
		for(auto it : Adj[u]){
			int v = it.fi;
			if(!vis[v]){
				vis[v] = 1;
				distt[v] = distt[u] + 1;
				q.push(v);
			}
		}
	}
///	dfs(S, 0);
//	for(auto it : ok) cout << it << " ";
//	cout << "\n";
	assert(ok.size());
	int le3 = 0, ri3 = ok.size() - 1;
	while(le3 < ri3){
		int mid = (le3 + ri3) >> 1;
		temp.resize(m);
		for(int i = 0; i < m; i++) temp[i] = 0;
		for(int i = 0; i <= mid; i++){
			int u = ok[i];
			for(auto it : Adj[u]) temp[it.se] = 1;
		}
		ll get = ask(temp);
		if(get == opt) le3 = mid + 1;
		else ri3 = mid; 
	}
	int T = ok[le3];
	answer(S, T);
	//answer((int)v1[(int)le2].fi, (int)v2[(int)le3].fi);
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t;
	cin >> t;
	while(t--) process();
}
#endif

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