Submission #1018721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018721		amirhoseinfar1385	Towns (IOI15_towns)	C++17	25 / 100	14 ms	508 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
long long n,inf=1e9;
map<pair<long long,long long>,long long>mp;
long long pors(long long u,long long v){
	if(u>v){
		swap(u,v);
	}
	if(mp.count(make_pair(u,v))==0){
		mp[make_pair(u,v)]=getDistance(u,v);
	}
	return mp[make_pair(u,v)];
}

pair<long long,long long>getdia(){
	vector<pair<long long,long long>>allv;
	for(long long i=1;i<n;i++){
		allv.push_back(make_pair(pors(0,i),i));
	}
	sort(allv.begin(),allv.end());
	long long u=allv.back().second;
	allv.clear();
	for(long long i=0;i<n;i++){
		if(i==u){
			continue;
		}
		allv.push_back(make_pair(pors(u,i),i));
	}
	sort(allv.begin(),allv.end());
	long long v=allv.back().second;
	return make_pair(u,v);
}

int hubDistance(int N,int sub) {
	mp.clear();
	n=N;
	sub=sub;
	pair<long long,long long>di=getdia();
//	cout<<di.first<<" "<<di.second<<" "<<pors(di.first,di.second)<<"\n";
	long long mn=pors(di.first,di.second);
	for(long long i=0;i<n;i++){
		if(i!=di.first&&i!=di.second){
			mn=min(mn,max(pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first))/2);
			if((pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second))%2==1||(pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first))%2==1){
				exit(23);
			}
//			cout<<pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second)<<" "<<pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first)<<"\n";
		}
	}
	return mn;
}

Compilation message (stderr)

towns.cpp: In function 'long long int pors(long long int, long long int)':
towns.cpp:11:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |   mp[make_pair(u,v)]=getDistance(u,v);
      |                                  ^
towns.cpp:11:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |   mp[make_pair(u,v)]=getDistance(u,v);
      |                                    ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:51:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |  return mn;
      |         ^~

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