Submission #787114

#	Time	Username	Problem	Language	Result	Execution time	Memory
787114		APROHACK	Highway Tolls (IOI18_highway)	C++17	51 / 100	130 ms	16320 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
ll m, n, a, b, largo;
vector<int>adj[100000];
vector<int>idx[100000];


void llenar(int dd, int ht, int v, vector<int>&w){
	for(int i = dd ; i <= ht ; i ++)w[i] = v;
}

void find_edje(int &ejeMedio, vector<int>&w){
	int li = 0, ls = m-1, pos;
	pos = (li + ls)/2;
	ll tried[130003];
	for(int i = 0 ; i < m ; i ++)tried[i] = -1;
	while(li + 1 < ls){
		llenar(0, m-1, 0, w);
		llenar(0, pos, 1, w);
		ll res = ask(w);
		tried[pos] = res;
		if(res > largo*a){
			ls = pos;
		}else{
			li = pos + 1;
		}
		pos = (li + ls ) / 2 ;
	}
	if(tried[li] == -1){
		llenar(0, m-1, 0, w);
		llenar(0, pos, 1, w);
		tried[li] = ask(w);
	}
	if(tried[li] > largo*a){
		ejeMedio = li;
	}else ejeMedio = ls;
}

vector<int>getEdjes(int dd, int banned, vector<int>&dist, vector<int>&nodes){
	queue<int>cola;
	dist.clear();
	nodes.clear();
	vector<int>ans;
	for(int i = 0 ; i < n ; i ++)dist.pb(INT_MAX);
	cola.push(dd);
	dist[dd] = 0;
	bool vis[n+1];
	memset(vis, false, sizeof vis);
	vis[dd] = true;
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(idx[cur][i] == banned)continue;
			if(vis[adj[cur][i]])continue;
			vis[adj[cur][i]] = true;
			dist[adj[cur][i]] = dist[cur] + 1;
			cola.push(adj[cur][i]);
			ans.pb(idx[cur][i]);
			nodes.pb(adj[cur][i]);
		}
	}
	
	return ans;
}

int cualAfecta(vector<int>&nodos, vector<int>&ejes, vector<int>&w){
	int li = 0, ls = ejes.size()-1;
	int pos = (li + ls)/2;
	while(li + 1 < ls){
		llenar(0, m-1, 0, w);
		for(int i = li ; i <= pos ; i ++)w[ejes[i]] = 1;
		if(ask(w) > largo*a){
			ls = pos;
		}else{
			li = pos + 1;
		}
		pos = (li + ls)/2;
	}
	if(li == ls)return nodos[li];
	llenar(0, m-1, 0, w);
	w[ejes[li]] = 1;
	if(ask(w) > largo * a)return nodos[li];
	else return nodos[ls];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	a = A;
	b = B;
	vector<int>w;
	for(int i = 0 ; i < m ; i ++){
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
		idx[U[i]].pb(i);
		idx[V[i]].pb(i);
		w.pb(0);
	}
	largo = ask(w)/a;
	int ejeMedio;
	find_edje(ejeMedio, w);
	//cout << ejeMedio << endl;
	//cout << U[ejeMedio] << " " << V[ejeMedio] << endl;
	
	
	vector<int>distancias, nodos, ejes;
	ejes = getEdjes(V[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	for(auto i : ejes)w[i] = 1;
	ll distkt = (ask(w)-largo*a)/(b-a);
	//cout << "dist " << V[ejeMedio] << " = " << distkt << endl;
	int s, t;
	if(distkt == 0){
		t = V[ejeMedio];
	}else{
		vector<int>tempNodos, tempEje;
		for(int i = 0 ; i < nodos.size() ; i ++){
			if(distancias[nodos[i]] == distkt){
				tempNodos.pb(nodos[i]);
				tempEje.pb(ejes[i]);
			}
		}
		//cout << " opciones " ;
		//for(auto i : tempNodos)cout << i << " " ;
		//cout << endl;
		
		t = cualAfecta(tempNodos, tempEje, w);
	}
	ejes = getEdjes(U[ejeMedio], ejeMedio, distancias, nodos);
	llenar(0, m-1, 0, w);
	for(auto i : ejes)w[i] = 1;
	distkt = (ask(w)-largo*a)/(b-a);
	//cout << "dist " << U[ejeMedio] << " = " << distkt << endl;
	
	if(distkt == 0){
		s = U[ejeMedio];
	}else{
		vector<int>tempNodos, tempEje;
		for(int i = 0 ; i < nodos.size() ; i ++){
			if(distancias[nodos[i]] == distkt){
				tempNodos.pb(nodos[i]);
				tempEje.pb(ejes[i]);
			}
		}
		
		s = cualAfecta(tempNodos, tempEje, w);
	}
	
	//cout << s << " " << t << endl;
	answer(s, t);
	

}

Compilation message (stderr)

highway.cpp: In function 'std::vector<int> getEdjes(int, int, std::vector<int>&, std::vector<int>&)':
highway.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~
highway.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for(int i = 0 ; i < nodos.size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~

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