oj.uz

Submission #383845

# Submission time Handle Problem Language Result Execution time Memory
383845 2021-03-30T21:19:11 Z MatheusLealV Towns (IOI15_towns) C++17
100 / 100
 25 ms 1292 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 16 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 23 ms 748 KB Output is correct
5 Correct 22 ms 748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 748 KB Output is correct
2 Correct 17 ms 748 KB Output is correct
3 Correct 24 ms 748 KB Output is correct
4 Correct 25 ms 748 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Output is correct
2 Correct 22 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 22 ms 780 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 748 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Output is correct
2 Correct 24 ms 1260 KB Output is correct
3 Correct 23 ms 1292 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 876 KB Output is correct
2 Correct 23 ms 1292 KB Output is correct
3 Correct 23 ms 1260 KB Output is correct