Submission #383845

#	Time	Username	Problem	Language	Result	Execution time	Memory
383845		MatheusLealV	Towns (IOI15_towns)	C++17	100 / 100	25 ms	1292 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n;
int dist[300][300];

int ct = 0;
int getDist(int a, int b){
	if(a == b) return 0;
	if(a>b)swap(a,b);
	if(dist[a][b] != -1)return dist[a][b];
	ct ++;
	assert(ct <= (7*n+1)/2);
	return dist[a][b]=dist[b][a]=getDistance(a,b);
}

int opt[2][300], u;
bool isEqual(int x, int y, int R){
	int A = getDist(x, y);
	int B = dist[u][x] + dist[u][y] - 2*R;
	if(A == B) return false;
	return true;
}
bool check(vector<int>&caras, int R){
	if(caras.size() <= n/2) return true;// nao tem majoritario

	vector<int> lista, bucket;
	for(auto x: caras){
		if(lista.empty() or !isEqual(lista.back(), x, R)){
			lista.pb(x);
			if(!bucket.empty()){
				lista.pb(bucket.back());
				bucket.pop_back();
			}
		}
		else{
			bucket.pb(x);
		}
	}
	int T = lista.back(), count = bucket.size();
	while(!lista.empty()){
		if(count > n/2) return false;
		//if((lista.size()) % 2 == 0 and bucket.empty()) return true; // nao tem majoritario
		if(isEqual(lista.back(), T, R)){
			lista.pop_back();
			count ++;
			if(!lista.empty()){
				lista.pop_back();
			}
		}
		else{
			lista.pop_back();
			if(!bucket.empty()) bucket.pop_back();
		}
	}
	if(count > n/2) return false;
	return true; // nao tem majoritario
}
int hubDistance(int nn, int sub) {
	// cout<<"solve "<<nn<<"\n";
	n = nn;
	int pei = 0;
	memset(dist,-1,sizeof dist);
	ct=0;
	pii maior = {-1,-1};
	//N-1
	for(int i = 1; i < n; i++){
		dist[0][i] = getDist(0, i);
		maior=max(maior, {dist[0][i], i});
	}
	int diametro = 0;
	//N-2
	for(int i = 0; i < n; i++){
		dist[maior.s][i] = getDist(maior.s, i);
		diametro=max(diametro, dist[maior.s][i]);
	}
	u = maior.s;
	int R = 1e9;
	vector<int> S;
	for(int i = 0; i < n; i++){
		int dx0 = (dist[0][u] + dist[0][i] - dist[u][i])/2;
		int dxu = dist[u][0] - dx0;
		opt[0][i] = dxu;
		opt[1][i] = diametro-dxu;
		R=min(R, max(dxu, diametro-dxu));
	}
	bool ans = false,esq=false,dir=false;
	// cout<<"NAOSDASODASDASDASDD\n";
	// cout<<"R = "<<R<<" u = "<<u<<"\n";
	// cout<<"SOLVE "<<n<<"\n";
	for(int i = 0; i < n; i++){
		vector<int> equal;
		if(opt[0][i] == R and !esq and !ans){ // left hub
			equal.clear();
			esq = 1;
			int dx0 = (dist[0][u] + dist[0][i] - dist[u][i])/2; // from 0 to x'
			int sz[2] = {0};
			for(int j = 0; j < n; j++){
				int dx0_=(dist[0][u] + dist[0][j] - dist[u][j])/2;
				if(dx0_ < dx0) sz[0] ++;
				else if(dx0_ > dx0) sz[1] ++;
				else equal.pb(j);
			}
			if(max(sz[0], sz[1]) > n/2) continue;
			bool cur = check(equal, R);
			// cout<<"LLLLLLLLLLLLLLLEFT "<<cur<<"\n";
			if(cur) ans=1;//,cout<<"ok from left\n";
			// cout<<"ll\n";
		}
		else if(opt[0][i] == diametro - R and !dir and !ans and diametro-R!=R){
			equal.clear();
			dir = 1;
			int dx0 = (dist[0][u] + dist[0][i] - dist[u][i])/2; // from 0 to x'
			int sz[2] = {0};
			for(int j = 0; j < n; j++){
				int dx0_=(dist[0][u] + dist[0][j] - dist[u][j])/2;
				if(dx0_ < dx0) sz[0] ++;
				else if(dx0_ > dx0) sz[1] ++;
				else equal.pb(j);
			}
			if(max(sz[0], sz[1]) > n/2) continue;
			bool cur = check(equal, diametro - R);
			// cout<<"LLLLLLLLLLLLLLLEFT "<<cur<<"\n";
			if(cur) ans=1;//, cout<<"ok from right\n";
			// cout<<"rr\n";
		}
	}
	// cout<<"END\n";
	// cout<<"SIZE = "<<" | "<<n<<" "<<ct<<"\n";
	//se ans = 1 -> algum nao tem majoritario
	// cout<<ans<<"\n";
	if(ans) R *= -1; 
	return -R;
}

Compilation message (stderr)

towns.cpp: In function 'bool check(std::vector<int>&, int)':
towns.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  if(caras.size() <= n/2) return true;// nao tem majoritario
      |     ~~~~~~~~~~~~~^~~~~~
towns.cpp:44:43: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   44 |  int T = lista.back(), count = bucket.size();
      |                                ~~~~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:6: warning: unused variable 'pei' [-Wunused-variable]
   66 |  int pei = 0;
      |      ^~~
towns.cpp:63:29: warning: unused parameter 'sub' [-Wunused-parameter]
   63 | int hubDistance(int nn, int sub) {
      |                         ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 39 / 39