Submission #783351

#	Time	Username	Problem	Language	Result	Execution time	Memory
783351		APROHACK	Highway Tolls (IOI18_highway)	C++14	6 / 100	190 ms	262144 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];
int totalA, totalB;
ll largo ;
int centro;
bool vis[100000];
bool banned[130005];
short color[130000];
int pintao[2]; // cuantos pintados de ese color
void reiniciar(){
	memset(vis, false, sizeof vis);
}

int hijos(int node, int parent){
	int cuantos = 0;
	int maxi = 0;
	vis[node] = true;
	for(int i = 0 ; i < adj[node].size() ; i ++){
		if(vis[adj[node][i]] or adj[node][i] == parent or banned[idx[node][i]])continue;
		int temp = hijos(adj[node][i], node);
		cuantos += temp;
		maxi = max(maxi, cuantos);
	}
	maxi = max(maxi, totalA-cuantos); // OJO
	if(maxi <= (totalA+1)/2){
		centro = node;
	}
	return cuantos+1;
}
void colorear(int node, int parent, short cual){
	for(int i = 0 ; i < adj[node].size() ; i ++){
		if(banned[idx[node][i]] or adj[node][i] == parent)continue;
		colorear(adj[node][i], node, cual);
		color[idx[node][i]] = cual;
	}
}

pair<int, int> distancia(int inicio, int fin1, int fin2){
	int dist[100000];
	for(int i = 0 ; i <= n ; i ++)dist[i] = INT_MAX;
	memset(vis, false, sizeof vis);
	queue<int>cola;
	dist[inicio] = 0;
	vis[inicio] = true;
	cola.push(inicio);
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		for(int i = 0 ; i < adj[cur].size() ; i ++){
			if(!vis[adj[cur][i]]){
				vis[adj[cur][i]] = true;
				dist[adj[cur][i]] = dist[cur] + 1;
				//cout << "distancia a " << adj[cur][i] << dist[adj[cur][i]] << endl;
				cola.push(adj[cur][i]);
			}
		}
	}
	return {dist[fin1], dist[fin2]};
}

bool canReach(int node, int parent, int dest){
	if(node == dest)return true;
	for(int i = 0 ; i < adj[node].size() ; i ++){
		if(adj[node][i] == parent)continue;
		if(canReach(adj[node][i], node, dest))return true;
	}
	return false;
}



void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  m = U.size();
  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);
  }
  n = N;
  totalA = n;
  vector<int>w;
  for(int i = 0 ; i < m ; i ++)w.pb(0);
  ll cuanto = ask(w);
  largo = cuanto / A;
  memset(banned, false, sizeof banned);
  centro = 0;
  vector<int>mitad1, mitad2, restantes;
  int centroFinal;
  while(true){
	  //hallar nodoCentral (centro)
	  reiniciar();
	  hijos(centro, -1);
	  reiniciar();
	  pintao[0] = 0;
	  pintao[1] = 0;
	  //cout << "centro " << centro << endl;
	  int guarCentro = centro;
	  for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
		  if(banned[idx[guarCentro][i]])continue;
		  int cuan = hijos(adj[guarCentro][i], guarCentro);
		  //cout << "adds " << cuan << endl;
		  if(cuan + pintao[0] <= (totalA+1)/2){
			  //cout << "pintando " << adj[guarCentro][i] << " " << cuan + pintao[0] << endl;
			  colorear(adj[guarCentro][i], guarCentro, 0);
			  color[idx[guarCentro][i]] = 0;
			  pintao[0] += cuan;
		  }else{
			  colorear(adj[guarCentro][i], guarCentro, 1);
			  color[idx[guarCentro][i]] = 1;
			  pintao[1] += cuan;
		  }
	  }
	  //cout << "!" << pintao[0] << " " << pintao[1] << endl;
	  
	  for(int i = 0 ; i < m ; i ++){
		  //cout << "color " << i << " = " << color[i] << endl;
		  w[i] = color[i];
	  }
	  ll resp = ask(w);
	  if(resp == (ll)A * largo or resp == (ll)B*largo){ // se dividio por completo.
		  //cout << "se dividio por completo " << endl;
		  if(resp == B*largo){
				totalA = pintao[1];
				totalB = pintao[0];
				for(int i = 0 ; i < m ; i ++){
					if(w[i] == 0)banned[i] = true;
				}
		  }else{
				totalA = pintao[0];
				totalB = pintao[1];
				for(int i = 0 ; i < m ; i ++){
					if(w[i] == 1)banned[i] = true;
				}
			}
			//cout << "quedaron " << totalA << endl;
			if(totalA == 1){
				for(int i = 0 ; i < m ; i ++){
					if(!banned[i]){
						answer(U[i], V[i]);
						return ;
					}
				}
			}
		  for(int i = 0 ; i < m ; i ++){
			  color[i] = 0;
		  }
	  }else{ // se dividio parcialmente.
		  //cout << "se dividio a la mita " << endl;
		  
		  for(int i = 0 ; i < m ; i ++){
			  if(!banned[i]){
				  restantes.pb(i);
				  if(color[i])mitad1.pb(i);
				  else mitad2.pb(i);
			  }
		  }
		  centroFinal = guarCentro;
		  break;
	  }
	  centro = guarCentro;
	  //break;
  }
  
  
  
  
	  int ansA, ansB;
	  for(int i = 0 ; i < m ; i ++)banned[i] = true;
	  for(int i = 0 ; i < mitad1.size() ; i ++)banned[mitad1[i]] = false;
	  totalA = mitad1.size();
	  for(int i = 0 ; i < m ; i ++){
			  color[i] = 0;
		  }
		centro = centroFinal;
		//int ip = 0;
  while(true){
	  //hallar nodoCentral (centro)
	  reiniciar();
	  hijos(centro, -1);
	  reiniciar();
	  pintao[0] = 0;
	  pintao[1] = 0;
	  //cout << "centro " << centro << endl;
	  int guarCentro = centro;
	  for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
		  if(banned[idx[guarCentro][i]])continue;
		  int cuan = hijos(adj[guarCentro][i], guarCentro);
		  //cout << "adds " << cuan << endl;
		  if((canReach(adj[guarCentro][i], guarCentro, centroFinal) and (pintao[0] + cuan <= (totalA+1)/2) )or (pintao[1] + cuan > (totalA+1)/2)){
			  colorear(adj[guarCentro][i], guarCentro, 0);
			  color[idx[guarCentro][i]] = 0;
			  pintao[0] += cuan;
		  }else{
			  colorear(adj[guarCentro][i], guarCentro, 1);
			  color[idx[guarCentro][i]] = 1;
			  pintao[1] += cuan;
		  }
	  }
	  //cout << "!" << pintao[0] << " " << pintao[1] << endl;
	  
	  for(int i = 0 ; i < m ; i ++){
		  //cout << "color " << i << " = " << color[i] << endl;
		  w[i] = color[i];
	  }
	  ll resp = ask(w);
	  
	  
	  if(resp > (ll)A*largo){ // le dio
			totalA = pintao[1];
			totalB = pintao[0];
			for(int i = 0 ; i < m ; i ++){
				if(w[i] == 0)banned[i] = true;
			}
	  }else{
			totalA = pintao[0];
			totalB = pintao[1];
			for(int i = 0 ; i < m ; i ++){
				if(w[i] == 1)banned[i] = true;
			}
		}
		//cout << "quedaron " << totalA << endl;
		if(totalA == 1){
			for(int i = 0 ; i < m ; i ++){
				if(!banned[i]){
					//cout << "opciones " << U[i] << " " <<  V[i] << endl;
					pair<int, int> distancias = distancia(centroFinal, U[i], V[i]);
					if(distancias.ff > distancias.ss)ansA = U[i];
					else ansA=V[i];
					break;
				}
			}
			break;
		}
	  for(int i = 0 ; i < m ; i ++){
		  color[i] = 0;
	  }
	  centro = guarCentro;
  }
  
  //return ;
  
  
  

  for(int i = 0 ; i < m ; i ++)banned[i] = true;
  for(int i = 0 ; i < mitad2.size() ; i ++)banned[mitad2[i]] = false;
  totalA = mitad2.size();
  for(int i = 0 ; i < m ; i ++){
		  color[i] = 0;
	  }
	centro = centroFinal;
  while(true){
	  //hallar nodoCentral (centro)
	  reiniciar();
	  hijos(centro, -1);
	  reiniciar();
	  pintao[0] = 0;
	  pintao[1] = 0;
	  //cout << "centro " << centro << endl;
	  int guarCentro = centro;
	  for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
		  if(banned[idx[guarCentro][i]])continue;
		  int cuan = hijos(adj[guarCentro][i], guarCentro);
		  ////////cout << "adds " << cuan << endl;
		  if(((canReach(adj[guarCentro][i], guarCentro, centroFinal) and (pintao[0] + cuan <= (totalA+1)/2))) or (pintao[1] + cuan > (totalA+1)/2)){
			  colorear(adj[guarCentro][i], guarCentro, 0);
			  color[idx[guarCentro][i]] = 0;
			  pintao[0] += cuan;
		  }else{
			  colorear(adj[guarCentro][i], guarCentro, 1);
			  color[idx[guarCentro][i]] = 1;
			  pintao[1] += cuan;
		  }
	  }
	  //cout << "!" << pintao[0] << " " << pintao[1] << endl;
	  
	  for(int i = 0 ; i < m ; i ++){
		  //cout << "color " << i << " = " << color[i] << endl;
		  w[i] = color[i];
	  }
	  ll resp = ask(w);
	  
	  
	  if(resp > (ll)A*largo){ // le dio
			totalA = pintao[1];
			totalB = pintao[0];
			for(int i = 0 ; i < m ; i ++){
				if(w[i] == 0)banned[i] = true;
			}
	  }else{
			totalA = pintao[0];
			totalB = pintao[1];
			for(int i = 0 ; i < m ; i ++){
				if(w[i] == 1)banned[i] = true;
			}
		}
		////cout << "quedaron " << totalA << endl;
		if(totalA == 1){
			for(int i = 0 ; i < m ; i ++){
				if(!banned[i]){
					//cout << "opciones " << U[i] << " " <<  V[i] << endl;
					pair<int, int> distancias = distancia(centroFinal, U[i], V[i]);
					if(distancias.ff > distancias.ss)ansB = U[i];
					else ansB=V[i];
					break;
				}
			}
			break;
		}
	  for(int i = 0 ; i < m ; i ++){
		  color[i] = 0;
	  }
	  centro = guarCentro;

  }
  
  
  ////cout << ansA << " " << ansB << endl;
  //asw(w);
  answer(ansA, ansB);
}

Compilation message (stderr)

highway.cpp: In function 'int hijos(int, int)':
highway.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0 ; i < adj[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void colorear(int, int, short int)':
highway.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0 ; i < adj[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> distancia(int, int, 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 'bool canReach(int, int, int)':
highway.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0 ; i < adj[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |    for(int i = 0 ; i < mitad1.size() ; i ++)banned[mitad1[i]] = false;
      |                    ~~^~~~~~~~~~~~~~~
highway.cpp:195:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |    for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:256:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |   for(int i = 0 ; i < mitad2.size() ; i ++)banned[mitad2[i]] = false;
      |                   ~~^~~~~~~~~~~~~~~
highway.cpp:271:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |    for(int i = 0 ; i < adj[guarCentro].size() ; i ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:330:9: warning: 'ansA' may be used uninitialized in this function [-Wmaybe-uninitialized]
  330 |   answer(ansA, ansB);
      |   ~~~~~~^~~~~~~~~~~~
highway.cpp:330:9: warning: 'ansB' may be used uninitialized in this function [-Wmaybe-uninitialized]

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