oj.uz

Submission #1018721

# Submission time Handle Problem Language Result Execution time Memory
1018721 2024-07-10T08:55:38 Z amirhoseinfar1385 Towns (IOI15_towns) C++17
25 / 100
 14 ms 508 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct
5 Correct 11 ms 436 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 11 ms 348 KB Output is correct
4 Correct 14 ms 348 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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