oj.uz

Submission #1018714

# Submission time Handle Problem Language Result Execution time Memory
1018714 2024-07-10T08:50:16 Z amirhoseinfar1385 Towns (IOI15_towns) C++17
0 / 100
 12 ms 604 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) {
	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:50:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |  return mn;
      |         ^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -