Submission #295466

#	Time	Username	Problem	Language	Result	Execution time	Memory
295466		amoo_safar	Highway Tolls (IOI18_highway)	C++17	100 / 100	339 ms	24628 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

vector<pii> G[N];
vector<int> H[N];
int E[N], dep[N], rem[N];
int T, fnt[N];

void DFS(int u, int p = -1, int d = 0){
	dep[u] = d;
	T ++;
	for(auto adj : H[u])
		if(adj != p)
			DFS(adj, u, d + 1);
	T ++;
	fnt[u] = T;
}

void find_pair(int _n, vector<int> U, vector<int> V, int A, int B){
	int n = _n;
	int m = U.size();
	//assert(m == n - 1);
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	vector<int> W(m, 0);
	ll dis = ask(W);

	int src = -1;

	cerr << "*&^%$ " << dis << '\n';
	vector<int> I2(n, 0);
	iota(all(I2), 0);
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	shuffle(all(I2), rng);

	{
		int L = 0, R = n;

		while(L + 1 < R){
			int mid = (L + R) >> 1;
			for(int i = 0; i < mid; i++) rem[I2[i]] = 1;
			for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
			//cerr << "^ " << mid << ' ';
			//for(auto x : W) cerr << x;
			//cerr << '\n';
			if(ask(W) > dis) R = mid;
			else L = mid;

			for(int i = 0; i < mid; i++) rem[I2[i]] = 0;
		}
		src = I2[L];
		for(int i = 0; i < L; i++) rem[I2[i]] = true;
	}
	//src = 0;
	cerr << "@ " << src << '\n';


	queue<int> Q;
	vector<int> D(n, n);
	D[src] = 0; Q.push(src);
	int fr;
	while(!Q.empty()){
		fr = Q.front(); Q.pop();
		for(auto ed : G[fr]){
			int adj = ed.F;
			if(rem[adj]) continue;
			if(D[adj] > D[fr] + 1){
				D[adj] = D[fr] + 1;
				H[fr].pb(adj);
				H[adj].pb(fr);
				//cerr << "E : " << fr << ' ' << adj << '\n';
				Q.push(adj);
			}
		}
	}



	DFS(src);
	vector<int> I;
	for(int i = 0; i < n; i++) if(D[i] == n) rem[i] = 1;

	for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);

	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});
	
	//cerr << "() " ;
	//for(auto x : I) cerr << x << ' ';
	//cerr << '\n';
	int st = -1, fn = -1;

	int L = 0, R = I.size();

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		//for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) rem[I[i]] = 1;
		for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);

		if(ask(W) > dis) R = mid;
		else L = mid;

		for(int i = 0; i < mid; i++) rem[I[i]] = 0;
	}
	st = I[L];
	for(int i = 0; i < L; i++) rem[I[i]] = 1;

	cerr << "!! " << st << '\n';
	if(1ll * A * D[st] == dis){
		answer(src, st);
		return ;
	}
	
	I.clear();
	for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);

	DFS(st);
	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});

	//cerr << "! " << st << ' ' << L << '\n';
	//cerr << "&&& ";
	//for(auto x : I) cerr << x;
	//cerr << '\n';
	assert(I.size() >= 2);
	//reverse(I.begin(), I.end() - 1);

	L = 0, R = I.size();

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		//for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) rem[I[i]] = 1;
		for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
		//cerr << "^ " << mid << ' ';
		//for(auto x : W) cerr << x;
		//cerr << '\n';
		if(ask(W) > dis) R = mid;
		else L = mid;

		for(int i = 0; i < mid; i++) rem[I[i]] = 0;
		//for(int i = 0; i < n; i++) cerr << rem[i];
		//cerr << '\n';
	}
	fn = I[L];
	cerr << "!! " << fn << '\n';
	assert(1ll * A * (D[fn] + D[st]) == dis);
	answer(st, fn);
	
}

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