Submission #784215

#	Time	Username	Problem	Language	Result	Execution time	Memory
784215		APROHACK	Highway Tolls (IOI18_highway)	C++14	18 / 100	110 ms	13304 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;
	bool val = true;
	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);
		if(U[i] != i)val = false;
		if(V[i] != i + 1)val = false;
	}
	vector<int>w;
	for(int i = 0 ; i < m ; i ++)w.pb(0);
	ll ans = ask(w);
	largo = ans / A;
	if(val){
		int ansA, ansB;
		int li = 0, ls = m-1, pos;
		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[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[ls] = 1;
		if(ask(w) > largo*A){
			ansA = V[ls];
		}else ansA = V[li];
		
		
		li = 0, ls = m-1, pos;
		pos = (li + ls )/2;
		while(li+1 < ls){
			for(int i = 0 ; i < m ; i ++)w[i] = 0;
			for(int i = li ; i <= pos ; i ++){
				w[i] = 1;
			}
			if(ask(w) > largo*A){
				ls = pos;
			}else{
				li = pos +1;
			}
			pos = (li + ls)/2;
		}
		for(int i = 0 ; i < m ; i ++)w[i] = 0;
		w[li] = 1;
		if(ask(w) > largo*A){
			ansB = U[li];
		}else ansB = U[ls];
		answer(ansA, ansB);
	}else{

		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 ++){
      |                   ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:78:24: warning: right operand of comma operator has no effect [-Wunused-value]
   78 |   li = 0, ls = m-1, pos;
      |                        ^

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