Submission #1058173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058173		ReLice	Highway Tolls (IOI18_highway)	C++17	90 / 100	151 ms	28732 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define pf push_front
#define sz size()
#define bc back()
#define pob pop_back()
#define pof pop_front()
#define fr first
#define sc second
using namespace std;
const ll N=2e5+7;
const ll inf=1e18;
vector<vector<array<ll,2>>> g(N), g2(N);
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	ll M = V.sz;
	ll s, t, rt;
	ll n = N;
	vll v, u;
	ll i;
	
	for(auto i : V) v.pb(i);
	for(auto i : U) u.pb(i);
	
	vector<int> w(M, 0);
	
	ll x = ask(w);
	
	for(i=0;i<M;i++){
		g[v[i]].pb({u[i], i});
		g[u[i]].pb({v[i], i});
	}
	
	{//getting vertex on the path
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 0);
			
			for(i=0;i<m;i++){
				for(auto [to, r] : g[n - i - 1]) w[r] = 1;
			}
			
			ll y = ask(w);
			
			if(y == x) l = m;
			else r = m;
		}
		
		rt = n - r;
	}
	
	vll p(n), d(n);
	vll pr(n), tour;
	vector<vll> dd(n);
	
	auto bfs = [&](ll s){
		for(i=0;i<n;i++){
			dd[i].clear();
			d[i] = inf;
			pr[i] = p[i] = -1;
		}
		
		queue<ll> q;
		q.push(s);
		d[s] = 0;
		
		while(q.size()){
			ll x = q.front();
			q.pop();
			
			dd[d[x]].pb(x);
			
			for(auto [to, r] : g[x]){
				if(d[to] > d[x] + 1){
					d[to] = d[x] + 1 ;
					pr[to] = r;
					p[to] = x;
					q.push(to);
				}
			}
		}
		
		tour.clear();
		for(i=0;i<n;i++){
			for(auto j : dd[i]) tour.pb(j);
		}
	};
	
	vll path;
	auto calc = [&](ll N){
		ll l = 0, r = N;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 30000;
			
			w.assign(M, 1);
			
			for(auto i : path) w[i] =0;
			
			//~ cout<<m<<endl;
			for(i=1;i<m;i++) {
				w[pr[tour[i]]] = 0;
				//~ cout<<v[pr[tour[i]]]<<' '<<u[pr[tour[i]]]<<endl;
			}
			
			ll y = ask(w);
				
			if(x == y) r = m;
			else l = m;
		}
		
		return r - 1;
	};
	
	bfs(rt);
	
	ll k = calc(n);
	s = tour[k];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	t = tour[calc(k)];
	
	answer(s, t);
}

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