Submission #295370

#	Time	Username	Problem	Language	Result	Execution time	Memory
295370		amoo_safar	Highway Tolls (IOI18_highway)	C++17	18 / 100	246 ms	20148 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){
	T ++;
	for(auto adj : H[u])
		DFS(adj);
	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';
	{
		int L = -1, R = n - 1;

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

	for(int i = 0; i < src; i++) rem[i] = true;

	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);
				//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 fnt[i] < fnt[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];
	if(1ll * A * D[st] == dis){
		answer(src, st);
		return ;
	}
	//cerr << "! " << st << ' ' << L << '\n';
	
	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]]);

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

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

	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: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31