oj.uz

Submission #133745

# Submission time Handle Problem Language Result Execution time Memory
133745 2019-07-21T09:19:35 Z Mahdi_Jfri Towns (IOI15_towns) C++14
61 / 100
 22 ms 452 KB 
#include "towns.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e2 + 20;

int h[2][maxn] , d[maxn] , p[maxn];

bool is[maxn];

vector<int> ver[maxn];

int root(int v)
{
	return p[v] < 0? v : p[v] = root(p[v]);
}

void merge(int a , int b)
{
	a = root(a) , b = root(b);
	if(a == b)
		return;

	p[a] += p[b];
	p[b] = a;
}

int hubDistance(int n, int sub)
{
	mt19937 rng(696980);
	memset(h , 0 , sizeof h);
	int ask = 0;
	for(int i = 1; i < n; i++)
		h[0][i] = getDistance(0 , i) , ask++;

	int a = max_element(h[0] , h[0] + n) - h[0];

	memset(h[0] , 0 , sizeof h[0]);
	for(int i = 0; i < n; i++)
		if(i != a)
			h[0][i] = getDistance(a , i) , ask++;

	int b = max_element(h[0] , h[0] + n) - h[0];
	for(int i = 0; i < n; i++)
		if(i != b)
			h[1][i] = getDistance(b , i) , ask++;

	vector<int> val;
	int ans = 1e9;
	for(int i = 0; i < n; i++)
	{
		int k = (h[0][i] - h[1][i] + h[0][b]) / 2;
		val.pb(k);
		d[i] = h[0][i] - k;
		ans = min(ans , max(k , h[0][b] - k));
	}

	sort(val.begin() , val.end());
	val.resize(unique(val.begin() , val.end()) - val.begin());

	int m = val.size();
	for(int i = 0; i < m; i++)
		ver[i].clear();

	for(int i = 0; i < n; i++)
	{
		int k = (h[0][i] - h[1][i] + h[0][b]) / 2;
		k = lower_bound(val.begin() , val.end() , k) - val.begin();
		ver[k].pb(i);
	}

	if(sub <= 2)
		return ans;

	bool has = 0;
	for(int i = 0; i < m; i++)
		if(max(val[i] , h[0][b] - val[i]) == ans)
		{
			int k = ver[i].size() , s1 = 0 , s2 = 0;
			for(int j = 0; j < i; j++)
				s1 += ver[j].size();
			s2 = n - k - s1;

			if(max(s1 , s2) > n / 2)
				continue;

			memset(p , -1 , sizeof p);

			int rem = k;
			bool f = 1;
			shuffle(ver[i].begin() , ver[i].end() , rng);
			for(int _ = 0; !ver[i].empty() && _ < 1e5 && ask < 5 * n; _++)
			{
				int j = rng() % (int)ver[i].size();
				int v = ver[i][j];
				ver[i].erase(ver[i].begin() + j);

				if(p[v] >= 0)
					continue;
				is[v] = 1;

				for(int l = 0; l < (int)ver[i].size() && -p[v] <= n / 2 && ask < 5 * n; l++)
				{
					int u = ver[i][l];
					if(p[u] < 0)
						ask++;
					if(p[u] < 0 && getDistance(v , u) != d[v] + d[u])
					{
						p[v] += p[u];
						p[u] = v;
					}
				}

				if(-p[v] > n / 2)
				{
					f = 0;
					break;
				}

				rem -= -p[v];
			}

			has |= f;
		}

	if(!has)
		ans = -ans;
	return ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:40:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int a = max_element(h[0] , h[0] + n) - h[0];
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:47:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  int b = max_element(h[0] , h[0] + n) - h[0];
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:65:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int m = val.size();
          ~~~~~~~~^~
towns.cpp:72:48: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   k = lower_bound(val.begin() , val.end() , k) - val.begin();
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
towns.cpp:83:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    int k = ver[i].size() , s1 = 0 , s2 = 0;
            ~~~~~~~~~~~^~
towns.cpp:85:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     s1 += ver[j].size();
                       ^
towns.cpp:98:19: warning: conversion to 'int' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type {aka long unsigned int}' may alter its value [-Wconversion]
     int j = rng() % (int)ver[i].size();
             ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 376 KB Output is correct
5 Correct 21 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 21 ms 452 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 22 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 376 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 21 ms 416 KB Output is correct
3 Correct 21 ms 376 KB Output is correct

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -