oj.uz

Submission #126131

# Submission time Handle Problem Language Result Execution time Memory
126131 2019-07-07T05:41:04 Z baluteshih Towns (IOI15_towns) C++14
48 / 100
 22 ms 1144 KB 
#include "towns.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int INF=1e9;
map<pii,int> mp;

int gD(int a,int b)
{
	if(a==b) return 0;
	if(a>b) swap(a,b);
	auto p=mp.find(MP(a,b));
	if(p!=mp.end()) return p->S;
	return mp[MP(a,b)]=getDistance(a,b);
}

int hubDistance(int N, int sub)
{
	mp.clear();
	vector<int> dis(N,0),a(N,0),b(N,0);
	int x,y,R=INF,RR;
	for(int i=1;i<N;++i)
		dis[i]=gD(0,i);
	x=max_element(ALL(dis))-dis.begin();
	for(int i=0;i<N;++i)
		a[i]=gD(x,i);
	y=max_element(ALL(a))-a.begin();
	for(int i=0;i<N;++i)
		b[i]=gD(y,i);
	for(int i=0;i<N;++i)
		R=min(R,abs(a[i]-b[i]));
	RR=(a[y]+R)/2;
	//cout << x << ' ' << y << "\n";
	if(sub==1||sub==2||sub==4)
	{
		int cnt[3]={};
		for(int i=0;i<N;++i)
			if(abs(a[i]-b[i])==R) ++cnt[0];
			else if(a[i]<b[i]) ++cnt[1];
			else ++cnt[2];
		if(cnt[0]<=N/2&&cnt[1]<=N/2&&cnt[2]<=N/2) return RR;
		return -RR;
	}
	else
	{
		vector<int> chk[2];
		int cnt[2]={};
		for(int i=0;i<N;++i)
			if(abs(a[i]-b[i])==R)
				if(a[i]<b[i]) chk[0].pb(i);
				else chk[1].pb(i);
			else if(a[i]<b[i]) ++cnt[0];
			else ++cnt[1];
		//for(int i=0;i<N;++i)
		//	cout << abs(a[i]-b[i]) << " ";
		//ET;
		if(chk[0].empty())
			chk[0].swap(chk[1]),swap(cnt[0],cnt[1]);
		//cout << cnt[0] << " " << chk[0].size() << "**\n";
		//cout << cnt[1] << " " << chk[1].size() << "***\n";
		if(chk[1].empty())
		{
			if(cnt[0]>N/2||cnt[1]>N/2) return -RR;
			while(chk[0].size())
			{
				int t=0;;
				vector<int> nxt;
				for(int i:chk[0])
					if(gD(i,chk[0][0])<max(a[chk[0][0]],b[chk[0][0]])-RR+max(a[i],b[i])-RR)
						++t;
					else
						nxt.pb(i);
				if(t>N/2) return -RR;
				nxt.swap(chk[0]);
			}
			return RR;
		}
		else
		{
			int flag1=1,flag2=1;
			if(cnt[1]+chk[1].size()>N/2) flag1=0;
			else 
			{
				while(chk[0].size())
				{
					int t=0;
					vector<int> nxt;
					for(int i:chk[0])
						if(gD(i,chk[0][0])<max(a[chk[0][0]],b[chk[0][0]])-RR+max(a[i],b[i])-RR)
							++t;
						else
							nxt.pb(i);
					if(t>N/2) flag1=0;
					nxt.swap(chk[0]);
				}
			}
			if(cnt[0]+chk[0].size()>N/2) flag2=0;
			else
			{
				while(chk[1].size())
				{
					int t=0;
					vector<int> nxt;
					for(int i:chk[1])
						if(gD(i,chk[1][0])<max(a[chk[1][0]],b[chk[1][0]])-RR+max(a[i],b[i])-RR)
							++t;
						else
							nxt.pb(i);
					if(t>N/2) flag2=0;
					nxt.swap(chk[1]);
				}
			}
			if(flag1||flag2) return RR;
			return -RR;
		}
	}
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:35:25: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  x=max_element(ALL(dis))-dis.begin();
    ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:38:23: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
  y=max_element(ALL(a))-a.begin();
    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
towns.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cnt[1]+chk[1].size()>N/2) flag1=0;
       ~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cnt[0]+chk[0].size()>N/2) flag2=0;
       ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 888 KB Output is correct
2 Correct 16 ms 808 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 21 ms 916 KB Output is correct
5 Correct 21 ms 888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 888 KB Output is correct
2 Correct 17 ms 888 KB Output is correct
3 Correct 21 ms 888 KB Output is correct
4 Correct 21 ms 916 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1016 KB Output is correct
2 Correct 22 ms 1016 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 22 ms 888 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1144 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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