oj.uz

Submission #1018783

# Submission time Handle Problem Language Result Execution time Memory
1018783 2024-07-10T09:45:21 Z amirhoseinfar1385 Towns (IOI15_towns) C++17
61 / 100
 13 ms 600 KB 
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
map<pair<int,int>,int>mp;
int pors(int u,int 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<int,int>getdia(){
	vector<pair<int,int>>allv;
	for(int i=1;i<n;i++){
		allv.push_back(make_pair(pors(0,i),i));
	}
	sort(allv.begin(),allv.end());
	int u=allv.back().second;
	allv.clear();
	for(int i=0;i<n;i++){
		if(i==u){
			continue;
		}
		allv.push_back(make_pair(pors(u,i),i));
	}
	sort(allv.begin(),allv.end());
	int v=allv.back().second;
	return make_pair(u,v);
}
 
int hubDistance(int N,int sub) {
	mp.clear();
	n=N;
	sub=sub;
	pair<int,int>di=getdia();
	int mn=pors(di.first,di.second);
	int ted1=0,ted2=0;
	vector<pair<int,int>>allv;
	for(int i=0;i<n;i++){
		if(i!=di.first&&i!=di.second){
			int fake1=pors(di.first,i)+pors(di.first,di.second)-pors(i,di.second),fake2=pors(di.second,i)+pors(di.second,di.first)-pors(i,di.first);
			fake1/=2;
			fake2/=2;
			if(max(fake1,fake2)==mn){
				allv.push_back(make_pair(fake1,i));
			}else if(max(fake1,fake2)<mn){
				allv.clear();
				allv.push_back(make_pair(fake1,i));
			}
			mn=min(mn,max(fake1,fake2));
			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);
			}
			if(fake1<fake2){
				ted1++;
			}else{
				ted2++;
			}
		}
	}
	sort(allv.begin(),allv.end());
	int wh=allv[0].second,tol=allv[0].first;
	if(allv[0].first!=allv.back().first){
		if(max(ted1,ted2)*2<=n){
			return mn;
		}else if(ted2*2>n){
			wh=allv.back().second;
			tol=allv.back().first;
		}
	}
	int cntnow=0,last=di.second,komak=di.first;
	if(sub==1||sub==2||sub==4){
		int cnt1=1,cnt2=0,cnt3=1,cnt=0;
		for(int i=0;i<n;i++){
			if(i==di.first||i==di.second){
				continue;
			}
			int z=(pors(di.first,di.second)+pors(di.first,i)-pors(i,di.second))/2;
			if(z<tol){
				cnt1++;
			}else if(z==tol){
				cnt2++;
			}else{
				cnt3++;
			}
		}
		if(max(cnt1,max(cnt2,cnt3))*2>n){
			return -mn;
		}
		return mn;
	}
	for(int i=0;i<n;i++){
		if(i==di.first||i==di.second){
			continue;
		}
		int z=(pors(komak,last)+pors(komak,i)-pors(i,last))/2;
		if(z>tol){
			cntnow++;
			continue;
		}else if(cntnow>0){
			cntnow--;
			continue;
		}
		cntnow++;
		last=i;
		if(z!=tol){
			komak=(di.first^di.second^komak);
			tol=pors(di.first,di.second)-tol;
		}
	}
	int cnt=1;
	for(int i=0;i<n;i++){
		if(i==last||i==komak){
			continue;
		}
		if((pors(last,komak)+pors(komak,i)-pors(last,i))/2>tol){
			cnt++;
		}
	}
	if(cnt*2>n){
		return -mn;
	}
	return mn;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:77:28: warning: unused variable 'cnt' [-Wunused-variable]
   77 |   int cnt1=1,cnt2=0,cnt3=1,cnt=0;
      |                            ^~~
towns.cpp:66:6: warning: variable 'wh' set but not used [-Wunused-but-set-variable]
   66 |  int wh=allv[0].second,tol=allv[0].first;
      |      ^~

Subtask #1
13.0 / 13.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 0 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct
5 Correct 11 ms 496 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 348 KB Output is correct
2 Correct 11 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 11 ms 348 KB Output is correct

Subtask #6
0 / 39.0

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