Submission #784213

#	Time	Username	Problem	Language	Result	Execution time	Memory
784213		APROHACK	Highway Tolls (IOI18_highway)	C++14	12 / 100	118 ms	13324 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;
int m, n;
vector<int>adj[100000];
vector<int>idx[100000];
vector<int>options;
vector<int>edjes;
bool vis[100000];
ll largo;
void bfs(int s){
	memset(vis, false, sizeof vis);
	int distancia[100000];
	queue<int>cola;
	distancia[0] = 0;
	vis[0] = true;
	cola.push(s);
	while(!cola.empty()){
		int cur = cola.front();
		//cout << cur << endl;
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(vis[adj[cur][i]])continue;
			vis[adj[cur][i]] = true;
			distancia[adj[cur][i]] = distancia[cur] + 1;
			if(distancia[adj[cur][i]] == largo){
				options.pb(adj[cur][i]);
				edjes.pb(idx[cur][i]);
			}
			cola.push(adj[cur][i]);
		}
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	n = N;
	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);
	}
	vector<int>w;
	for(int i = 0 ; i < m ; i ++)w.pb(0);
	ll ans = ask(w);
	largo = ans / A;
	
	bfs(0);
	int li = 0, ls = options.size()-1;
	int pos = (li + ls)/2;
	while(li + 1 < ls){
		for(int i = 0 ; i < m ; i ++)w[i] = 0;
		for(int i = pos ; i <= ls ; i ++)w[edjes[i]] = 1;
		if(ask(w) > largo*A){
			li = pos;
		}else{
			ls = pos -1;
		}
		pos = (li + ls )/2;
	}
	for(int i = 0 ;  i < m ; i ++)w[i] = 0;
	w[edjes[li]] = 1;
	if(ask(w) > largo*A)answer(0, options[li]);
	else answer(0, options[ls]);
	
}

Compilation message (stderr)

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

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