Submission #725126

#	Time	Username	Problem	Language	Result	Execution time	Memory
725126		FatihSolak	Highway Tolls (IOI18_highway)	C++17	51 / 100	174 ms	25956 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];
int vis[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 << "EDGE:";
	// cout << u[l] << ' ' << v[l] << endl;
	queue<int> q;
	vis[u[l]] = 1;
	vis[v[l]] = 1;
	q.push(u[l]);
	q.push(v[l]);
	while(q.size()){
		auto tp = q.front();
		q.pop();
		for(auto u:adj[tp]){
			if(vis[u.first]){
				continue;
			}
			vis[u.first] = 1;
			adj2[tp].push_back(u);
			q.push(u.first);
		}
	}
	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);
}
/*
7 6 4 18 2 3
1 0
2 0
3 0
4 1
5 2
6 5
*/

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