Submission #800025

#	Time	Username	Problem	Language	Result	Execution time	Memory
800025		Ronin13	Towns (IOI15_towns)	C++17	100 / 100	332 ms	32208 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define ll long long 
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 1000001;

vector <vector <int> > vec(nmax);
vector <int> p(nmax), sz(nmax);
void make_set(int v){
	p[v] = v;
	sz[v] = 1;
}

int find_set(int v){
	return p[v] == v ? v : p[v] = find_set(p[v]);
}

void union_sets(int a, int b){
	a = find_set(a);
	b = find_set(b);
	if(a == b) return;
	p[b] = a;
	sz[a] += sz[b];
}

int hubDistance(int n, int sub) {
	for(int i= 0; i <= 1000000; i++){
		vec[i].clear();
	}
	int A;
	int d[n][2];
	d[0][0] = 0;
	A = 0;
	for(int i = 1; i < n; i++){
		d[i][0] = getDistance(0, i);
		if(d[i][0] > d[A][0]){
			A = i;
		}
	}
	//return A;
	int diam = 0;
	d[A][1] = 0;
	for(int i = 0; i < n; i++){
		if(A != i)
		d[i][1] = getDistance(A, i);
		//return getDistance(i, A);
		diam = max(d[i][1], diam);
	}
	
	int r = 1e9 + 1;
	for(int i = 0; i < n; i++){
		int a = d[i][1] + d[0][1] - d[i][0]; a >>= 1;
		vec[a].pb(i);
		r = min(r, max(diam - a, a));
	}
	vector <int> u;
	int cnt = 0;
	int cnd = -1;
	for(int i = 0; i <= 1000000; i++){
		if(vec[diam - r].empty()) continue;
		if(i >= diam - r) cnt += vec[i].size();
	}
	if(n - cnt <= n / 2) cnd =  diam - r;
	//cout << cnd << "\n";
	cnt = 0;
	for(int i = 0; i <= 1000000; i++){
		if(vec[r].empty()) continue;
		if(i >=r) cnt += vec[i].size();
	}
	if(n - cnt <= n / 2) cnd = r;
	if(cnd == -1){
		return -r;
	}
	//cout << cnd << "\n";
	vector <int> dead;
	vector <int> alive;
	for(int i = 0; i <= 1000000; i++){
		if(i >= cnd){
			for(int j = 0; j < vec[i].size(); j++)
				alive.pb(vec[i][j]);
		}
	}
	for(int i = 0; i < alive.size(); i++){
		make_set(alive[i]);
	}
	
	//vector <int> left;
	int left = -1;
	int cntq = 2 * n - 2;
	while(!alive.empty()){
		vector <int> nw;
		for(int i = 0; i < (int)alive.size() - 1; i+=2){
			int x = alive[i], y = alive[i + 1];
			//if(cntq == 7 * n / 2) return r;
			int len = getDistance(x, y);
			//cntq++;
			int v = d[x][1] + d[y][1] - len;
			if(v == 2 * cnd){
				dead.pb(x); dead.pb(y);
			}
			else union_sets(x, y), nw.pb(x);
		}
		if(alive.size() % 2 == 1){
			if(left != -1) dead.pb(left);
			left = alive.back();
		}
		swap(nw, alive);
	}
	if(left == -1) return r;
	cnt = sz[left];
	for(int i = 0; i < dead.size(); i++){
		int o = dead[i];
	//	if(cntq == 7 * n / 2) return r;
		int len = getDistance(o, left);
	//	cntq++;
		int v = d[o][1] + d[left][1] - len;
		if(v > 2 * cnd){
			cnt += sz[o];
		}
	}
	if(cnt > n / 2)return -r;
	return r;
	
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:69:40: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |   if(i >= diam - r) cnt += vec[i].size();
      |                                        ^
towns.cpp:76:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   76 |   if(i >=r) cnt += vec[i].size();
      |                                ^
towns.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(int j = 0; j < vec[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~
towns.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < alive.size(); i++){
      |                 ~~^~~~~~~~~~~~~~
towns.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i = 0; i < dead.size(); i++){
      |                 ~~^~~~~~~~~~~~~
towns.cpp:97:6: warning: unused variable 'cntq' [-Wunused-variable]
   97 |  int cntq = 2 * n - 2;
      |      ^~~~
towns.cpp:34:28: warning: unused parameter 'sub' [-Wunused-parameter]
   34 | int hubDistance(int n, 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