Submission #725625

#	Time	Username	Problem	Language	Result	Execution time	Memory
725625		FatihSolak	Highway Tolls (IOI18_highway)	C++17	51 / 100	190 ms	27580 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[N];
vector<pair<int,int>> adj2[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = u.size();
	vector<int> w(m,0);
	long long len = ask(w) / a;
	int l = 0,r = m-1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = l;i<=m;i++){
			w[i] = 1;
		}
		if(ask(w) != len * a){
			for(int i = l;i<=m;i++){
				w[i] = 0;
			}
			r = m;
		}
		else l = m + 1;
	}
	for(int i = 0;i<m;i++){
		adj[u[i]].push_back({v[i],i});
		adj[v[i]].push_back({u[i],i});
	}
	// cout << "LEN:";
	// cout << len << endl;
	// cout << "EDGE:";
	// cout << u[l] << ' ' << v[l] << endl;
	queue<int> q;
	auto bfs = [&](int v){
		vector<int> d(n,-1);
		vector<pair<int,int>> par(n,{-1,-1});
		queue<int> q;
		q.push(v);
		d[v] = 0;
		while(q.size()){
			auto tp = q.front();
			q.pop();
			for(auto u:adj[tp]){
				if(d[u.first] == -1){
					d[u.first] = d[tp] + 1;
					par[u.first] = {tp,u.second};
					q.push(u.first);
				}
			}
		}
		return make_pair(d,par);
	};
	auto x1 = bfs(u[l]);
	auto x2 = bfs(v[l]);
	for(int i = 0;i<n;i++){
		if(x1.first[i] < x2.first[i]){
			if(x1.second[i].first != -1){
				adj2[x1.second[i].first].push_back({i,x1.second[i].second});
			}
		}
		if(x2.first[i] < x1.first[i]){
			if(x2.second[i].first != -1){
				adj2[x2.second[i].first].push_back({i,x2.second[i].second});
			}
		}
	}
	function<void(int)> dfs = [&](int v)->void{
		for(auto u:adj2[v]){
			w[u.second] = 0;
			dfs(u.first);
		}
	};
	w.assign(m,1);
	dfs(u[l]);
	long long dep1 = (len * b - ask(w))/(b-a);
	long long dep2 = len  - 1 - dep1;
	// cout <<"DEP:";
	// cout << dep1 << ' ' << dep2 << endl;
	function<void(int,int,vector<pair<int,int>> &)> dfs2 = [&](int v,int target,vector<pair<int,int>> &x)->void{
		for(auto u:adj2[v]){
			if(target > 0)
				w[u.second] = 0;
			if(target == 1){
				x.push_back(u);
			}
			dfs2(u.first,target - 1,x);
		}
	};
	int s = -1;
	int t = -1;
	if(dep1 == 0)
		s = u[l];
	if(dep2 == 0)
		t = v[l];
	if(s == -1){
		vector<pair<int,int>> x;
		w.assign(m,1);
		dfs2(u[l],dep1,x);
		while(x.size() > 1){
			vector<pair<int,int>> tmp;
			while(tmp.size() < x.size()){
				tmp.push_back(x.back());
				x.pop_back();
			}
			for(auto u:tmp){
				w[u.second] = 1;
			}
			if(ask(w) != (dep2 + 1) * b + dep1 * a){
				for(auto u:tmp){
					w[u.second] = 0;
				}
				x = tmp;
			}
		}
		s = x[0].first;
	}
	if(t == -1){
		vector<pair<int,int>> x;
		w.assign(m,1);
		dfs2(v[l],dep2,x);
		// cout << "CAND:";
		// for(auto u:x){
		// 	cout << u.first << ' ';
		// }
		// cout << endl;
		while(x.size() > 1){
			vector<pair<int,int>> tmp;
			while(tmp.size() < x.size()){
				tmp.push_back(x.back());
				x.pop_back();
			}
			for(auto u:tmp){
				w[u.second] = 1;
			}
			if(ask(w) != (dep1 + 1) * b + dep2 * a){
				for(auto u:tmp){
					w[u.second] = 0;
				}
				x = tmp;
			}
		}
		t = x[0].first;
	}
	// cout << "HEY";
	// cout << s << ' ' << t << endl;
	answer(s,t);
}
/*
11 14 18 27 10 8
1 0
2 0
3 2
4 3
5 1
6 3
7 1
8 6
9 2
10 9
6 2
2 7
8 5
8 3
*/

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