Submission #785726

#	Time	Username	Problem	Language	Result	Execution time	Memory
785726		fatemetmhr	도시들 (IOI15_towns)	C++17	48 / 100	13 ms	1264 KiB

towns

//  ~ Be Name Khoda ~  //

#include "towns.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  200;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;


ll dis1[maxn5], dis2[maxn5], val[maxn5], keep[maxn5][maxn5];
ll len[maxn5];

ll gdis(int a, int b){
	if(a == b)
		return 0;
	if(keep[a][b] != -1)
		return keep[a][b];
	return keep[a][b] = keep[b][a] = getDistance(a, b);
}

int hubDistance(int n, int sub){
	memset(keep, -1, sizeof keep);
	int v = 0;
	dis1[0] = 0;
	for(int i = 1; i < n; i++){
		dis1[i] = gdis(0, i);
		if(dis1[i] >= dis1[v])
			v = i;
	}
	dis2[v] = 0;
	int u = v;
	for(int i = 0; i < n; i++){
		dis2[i] = gdis(v, i);
		if(dis2[i] >= dis2[u])
			u = i;
	}
	for(int i = 0; i < n; i++){
		dis1[i] = gdis(u, i);
	}
	int mnid = 0;
	for(int i = 0; i < n; i++){
		val[i] = abs(dis1[i] - dis2[i]);
		if(val[i] <= val[mnid])
			mnid = i;
	}
	for(int i = 0; i < n; i++)
		len[i] = (dis1[i] + dis2[i] - dis1[v]) / 2;
	ll R = max(dis1[mnid], dis2[mnid]) - len[mnid];
	if(sub <= 2)
		return R;
	ll x = R;
	int c = dis1[mnid] > dis2[mnid] ? u : v;
	if(c == v){
		for(int i = 0; i < n; i++)
			swap(dis1[i], dis2[i]);
		swap(u, v);
	}
	if(sub == 3){
		int num[3] = {0, 0, 0};
		vector <int> av, tmp;
		av.clear(); tmp.clear();
		for(int i = 0; i < n; i++){
			if(dis1[i] - len[i] == x){
				num[0]++;
				av.pb(i);
			}
			else if(dis1[i] - len[i] > x)
				num[1]++;
			else if(dis1[i] - len[i] < x)
				num[2]++;
		}
		//cout << "ha? " << num[1] << ' ' << num[2] << ' ' << num[0] << endl;
		if(max({num[1], num[2]}) <= n / 2){
			while(true){
				//cout << "hey " << av.size() << endl;
				if(av.size() <= n / 2)
					return R;
				num[0] = num[1] = 0;
				tmp.clear();
				int x = av.back();
				for(auto u : av){
					if(gdis(u, x) == len[u] + len[x])
						tmp.pb(u);
					else
						num[1]++;
				}
				if(num[1] > n / 2)
					break;
				av.clear();
				for(auto u : tmp)
					av.pb(u);
			}
		}
		bool re = false;
		for(int i = 0; i < n; i++){
			if(dis2[i] - len[i] == x && (true || dis1[i] - len[i] > x)){
				//cout << i << ' ' << x << ' ' << dis2[i] - len[i] << ' ' << dis1[i] - len[i] << ' ' << dis1[v] << endl;
				re = true;
			}
		}
		//cout << "here " << re << endl;
		if(re){
			int num[3] = {0, 0, 0};
			av.clear();
			tmp.clear();
			for(int i = 0; i < n; i++){
				if(dis2[i] - len[i] == x){
					num[0]++;
					av.pb(i);
				}
				else if(dis2[i] - len[i] > x)
					num[1]++;
				else if(dis2[i] - len[i] < x)
					num[2]++;
			}
			if(max({num[1], num[2]}) <= n / 2){
				while(true){
					if(av.size() <= n / 2)
						return R;
					num[0] = num[1] = 0;
					tmp.clear();
					int x = av.back();
					for(auto u : av){
						if(gdis(u, x) == len[u] + len[x])
							tmp.pb(u);
						else
							num[1]++;
					}
					if(num[1] > n / 2)
						break;
					av.clear();
					for(auto u : tmp)
						av.pb(u);
				}
			}
		}
		return -R;
	}
	int num[3] = {0, 0, 0};
	for(int i = 0; i < n; i++){
		ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
		if(dis1[i] - len == x)
			num[0]++;
		else if(dis1[i] - len > x)
			num[1]++;
		else if(dis1[i] - len < x)
			num[2]++;
	}
	if(max({num[0], num[1], num[2]}) <= n / 2)
		return R;
	bool re = false;
	for(int i = 0; i < n; i++){
		ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
		if(dis2[i] - len == x && dis1[i] - len > x)
			re = true;
	}
	if(re){
		int num[3] = {0, 0, 0};
		for(int i = 0; i < n; i++){
			ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
			if(dis2[i] - len == x)
				num[0]++;
			else if(dis2[i] - len > x)
				num[1]++;
			else if(dis2[i] - len < x)
				num[2]++;
		}
		if(max({num[0], num[1], num[2]}) <= n / 2)
			return R;
	}
	return -R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:67:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   67 |   return R;
      |          ^
towns.cpp:93:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |     if(av.size() <= n / 2)
      |        ~~~~~~~~~~^~~~~~~~
towns.cpp:94:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |      return R;
      |             ^
towns.cpp:97:9: warning: declaration of 'x' shadows a previous local [-Wshadow]
   97 |     int x = av.back();
      |         ^
towns.cpp:68:5: note: shadowed declaration is here
   68 |  ll x = R;
      |     ^
towns.cpp:98:14: warning: declaration of 'u' shadows a previous local [-Wshadow]
   98 |     for(auto u : av){
      |              ^
towns.cpp:48:6: note: shadowed declaration is here
   48 |  int u = v;
      |      ^
towns.cpp:107:14: warning: declaration of 'u' shadows a previous local [-Wshadow]
  107 |     for(auto u : tmp)
      |              ^
towns.cpp:48:6: note: shadowed declaration is here
   48 |  int u = v;
      |      ^
towns.cpp:120:8: warning: declaration of 'num' shadows a previous local [-Wshadow]
  120 |    int num[3] = {0, 0, 0};
      |        ^~~
towns.cpp:76:7: note: shadowed declaration is here
   76 |   int num[3] = {0, 0, 0};
      |       ^~~
towns.cpp:135:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |      if(av.size() <= n / 2)
      |         ~~~~~~~~~~^~~~~~~~
towns.cpp:136:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |       return R;
      |              ^
towns.cpp:139:10: warning: declaration of 'x' shadows a previous local [-Wshadow]
  139 |      int x = av.back();
      |          ^
towns.cpp:68:5: note: shadowed declaration is here
   68 |  ll x = R;
      |     ^
towns.cpp:140:15: warning: declaration of 'u' shadows a previous local [-Wshadow]
  140 |      for(auto u : av){
      |               ^
towns.cpp:48:6: note: shadowed declaration is here
   48 |  int u = v;
      |      ^
towns.cpp:149:15: warning: declaration of 'u' shadows a previous local [-Wshadow]
  149 |      for(auto u : tmp)
      |               ^
towns.cpp:48:6: note: shadowed declaration is here
   48 |  int u = v;
      |      ^
towns.cpp:154:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |   return -R;
      |          ^~
towns.cpp:158:6: warning: declaration of 'len' shadows a global declaration [-Wshadow]
  158 |   ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
      |      ^~~
towns.cpp:28:4: note: shadowed declaration is here
   28 | ll len[maxn5];
      |    ^~~
towns.cpp:167:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |   return R;
      |          ^
towns.cpp:170:6: warning: declaration of 'len' shadows a global declaration [-Wshadow]
  170 |   ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
      |      ^~~
towns.cpp:28:4: note: shadowed declaration is here
   28 | ll len[maxn5];
      |    ^~~
towns.cpp:175:7: warning: declaration of 'num' shadows a previous local [-Wshadow]
  175 |   int num[3] = {0, 0, 0};
      |       ^~~
towns.cpp:156:6: note: shadowed declaration is here
  156 |  int num[3] = {0, 0, 0};
      |      ^~~
towns.cpp:177:7: warning: declaration of 'len' shadows a global declaration [-Wshadow]
  177 |    ll len = (dis1[i] + dis2[i] - dis1[v]) / 2;
      |       ^~~
towns.cpp:28:4: note: shadowed declaration is here
   28 | ll len[maxn5];
      |    ^~~
towns.cpp:186:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  186 |    return R;
      |           ^
towns.cpp:188:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  188 |  return -R;
      |         ^~

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