Submission #725654

#	Time	Username	Problem	Language	Result	Execution time	Memory
725654		FatihSolak	Highway Tolls (IOI18_highway)	C++17	51 / 100	224 ms	14500 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[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<int> par(n,-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] = u.second;
					q.push(u.first);
				}
			}
		}
		return make_pair(d,par);
	};
	auto x1 = bfs(u[l]);
	auto x2 = bfs(v[l]);
	vector<int> ord1;
	vector<int> ord2;
	for(int i = 0;i<n;i++){
		if(x1.first[i] < x2.first[i]){
			ord1.push_back(i);
		}
		else if(x2.first[i] < x1.first[i]){
			ord2.push_back(i);
		}
		else{
			for(auto u:adj[i])
				w[u.second] = 1;
		}
	}
	sort(ord1.begin(),ord1.end(),[&](int a,int b){
		return x1.first[a] < x1.first[b];
	});
	sort(ord2.begin(),ord2.end(),[&](int a,int b){
		return x2.first[a] < x2.first[b];
	});
	// for(int i = 0;i<m;i++){
	// 	if(w[i] == 0){
	// 		cout << "EDGES:";
	// 		cout << u[i] << ' ' << v[i] << endl;
	// 	}
	// }
	// cout << "FIRST COMP";
	// for(auto u:ord1){
	// 	cout << u << ' ';
	// }
	// cout << endl;
	// cout << "SECOND COMP";
	// for(auto u:ord2){
	// 	cout << u << ' ';
	// }
	// cout << endl;
	int s = -1;
	int t = -1;
	l = 0, r = (int)ord1.size() - 1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = m+1;i<=r;i++){
			w[x1.second[ord1[i]]] = 1;
		}
		if(ask(w) == len * a){
			r = m;
		}
		else{
			for(int i = m+1;i<=r;i++){
				w[x1.second[ord1[i]]] = 0;
			}
			l = m+1;
		}
	}
	s = ord1[l];
	l = 0, r = (int)ord2.size() - 1;
	while(l < r){
		int m = (l + r)/2;
		for(int i = m+1;i<=r;i++){
			w[x2.second[ord2[i]]] = 1;
		}
		if(ask(w) == len * a){
			r = m;
		}
		else{
			for(int i = m+1;i<=r;i++){
				w[x2.second[ord2[i]]] = 0;
			}
			l = m+1;
		}
	}
	t = ord2[l];
	answer(s,t);
}
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
/*
11 12 16 19 9 10
1 0
2 0
3 1
4 0
5 4
6 3
7 4
8 4
9 5
10 1
9 3
5 1
*/

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