Submission #349623

#	Time	Username	Problem	Language	Result	Execution time	Memory
349623		tengiz05	Highway Tolls (IOI18_highway)	C++17	90 / 100	434 ms	24240 KiB

highway

#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<ll,ll>
typedef long long ll;
const int _N = 90005;
vector<int> edges[_N];
vector<pii> edge[_N];
vector<pii> EDGES;
int n, m, a, b;
ll dist;
pii num(ll x){
	ll dif = x-dist;
	assert(dif%(b-a)==0);
	return {dist - dif/(b-a),dif/(b-a)};
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	a=A,b=B;
	for(int i=0;i<m;i++){
		edges[U[i]].pb(V[i]);
		edges[V[i]].pb(U[i]);
		edge[U[i]].pb({V[i],i});
		edge[V[i]].pb({U[i],i});
		EDGES.pb({U[i],V[i]});
	}
	vector<int> toask(m,0);
	ll TMP = ask(toask);
	dist = TMP;
	int l=0,r=m-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[i] = 1;
		for(int i=mid+1;i<m;i++)toask[i] = 0;
		ll tmp = ask(toask);
		if(tmp == dist)l = mid+1;
		else r = mid;
	}
	int root = EDGES[l].first;
	
	
	vector<int> should_be_B;
	vector<int> prohibited(m,0);
	{
		queue<pii> q;
		vector<int> Dist(n,2e9);Dist[root] = 0;
		q.push({root,root});
		while(!q.empty()){
			auto [u, p] = q.front();q.pop();
			for(auto [to, ind] : edge[u]){
				if(to == p)continue;
				if(Dist[to] <= Dist[u]+1){
					should_be_B.pb(ind);
					prohibited[ind] = 1;
				}else if(Dist[to] == 2e9){
					Dist[to] = Dist[u] + 1;
					q.push({to, u});
				}
			}
		}
	}
	
	//~ cout << EDGES[l].first << ';' << EDGES[l].second << '\n';
	//~ cout << l << '-' << r << '\n';
	queue<int> q;
	vector<bool> used(n,0);
	q.push(root);used[root] = true;
	vector<int> v;
	vector<pii> vse;
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to] || prohibited[ind])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		for(auto x : should_be_B)toask[x] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	//~ cout << l << '-' << r << '\n';
	//~ cout << EDGES[v[l]].first << ' ' << EDGES[v[l]].second << '\n';
	//~ for(auto [x, y] : vse){
		//~ cout << x << ';' << y << '\n';
	//~ }
	prohibited.assign(m,0);
	should_be_B.clear();

	int s = vse[l].second;
	root = s;
	{
		queue<pii> q;
		vector<int> Dist(n,2e9);Dist[root] = 0;
		q.push({root,root});
		while(!q.empty()){
			auto [u, p] = q.front();q.pop();
			for(auto [to, ind] : edge[u]){
				if(to == p)continue;
				if(Dist[to] <= Dist[u]+1){
					should_be_B.pb(ind);
					prohibited[ind] = 1;
				}else if(Dist[to] == 2e9){
					Dist[to] = Dist[u] + 1;
					q.push({to, u});
				}
			}
		}
	}
	vse.clear();
	used.assign(n,0);
	q.push(root);used[root] = true;
	v.clear();
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		for(auto x : should_be_B)toask[x] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	int t = vse[l].second;
	//~ cout << s << ' ' << t << '\n';
	answer(s,t);
	
	return;
}


/*


7 6
1 2
3 4
0 2
0 3
3 4
2 6
2 5
2 1


5 4
1 2
4 2
0 1
0 2
0 3
0 4

3 2
100000 1000000000
0 1
1 2
1 0

*/

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