oj.uz

Submission #113294

# Submission time Handle Problem Language Result Execution time Memory
113294 2019-05-24T19:26:09 Z TadijaSebez Towns (IOI15_towns) C++11
100 / 100
 28 ms 1060 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=120;
int n,cen,den;
int a[N],b[N],len[N],pl[N];
int d[N][N],diam;
bool was[N][N];
int Ask(int i, int j)
{
	if(i==j) return 0;
	if(!was[i][j]) d[i][j]=d[j][i]=getDistance(i,j);
	was[i][j]=was[j][i]=1;
	return d[i][j];
}
bool Compare(int u, int v)
{
	return len[u]+len[v]!=Ask(u,v);
}
bool Try(int d)
{
	vector<int> work;
	int lo=1,hi=0;
	for(int i=0;i<n;i++) if(i!=cen)
	{
		int tmp=pl[i];
		if(tmp<d) lo++;
		if(tmp>d) hi++;
		if(tmp==d) work.pb(i);
	}
	if(lo>n/2 || hi>n/2) return 0;

	//Boyer-Moore majority vote algorithm

	vector<int> store,sz;
	vector<int> ok(work.size(),0);
	int balance=0;
	for(int i=0;i<work.size();i++)
	{
		if(balance==0) store.pb(i),sz.pb(1),balance++;
		else
		{
			if(Compare(work[i],work[store.back()]))
			{
				balance++;
				ok[i]=1;
				sz[sz.size()-1]++;
			}
			else balance--;
		}
	}
	int last=work[store.back()];
	int cnt=sz.back();
	for(int i=0;i+1<store.size();i++)
	{
		if(Compare(work[store[i]],last)) cnt+=sz[i];
		else
		{
			for(int j=store[i];j<store[i+1];j++) if(!ok[j])
			{
				if(Compare(work[j],last)) cnt++;
			}
		}
	}
	return cnt<=n/2;
}
int hubDistance(int _N, int sub)
{
	srand(time(0));
	n=_N;cen=den=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) was[i][j]=0;
	for(int i=0;i<n;i++) a[i]=b[i]=0;
	for(int i=1;i<n;i++)
	{
		a[i]=Ask(0,i);
		if(a[i]>a[cen]) cen=i;
	}
	for(int i=0;i<n;i++) if(i!=cen)
	{
		b[i]=Ask(cen,i);
		if(b[i]>b[den]) den=i;
	}
	diam=b[den];
	int pre=(a[cen]-a[den]+b[den])/2;
	int ans=diam,goal=diam/2;
	for(int i=0;i<n;i++) if(i!=cen)
	{
		pl[i]=(a[cen]+b[i]-a[i])/2;
		int tmp=pl[i];
		if(tmp<=pre)
		{
			if(abs(ans-goal)>abs(tmp-goal)) ans=tmp;
		}
		len[i]=(a[i]+b[i]-a[cen])/2;
	}
	bool ok=0;
	if(Try(ans) || Try(diam-ans)) ok=1;
	ans=max(ans,diam-ans);
	if(ok) return ans;
	else return -ans;
}

Compilation message

towns.cpp: In function 'bool Try(int)':
towns.cpp:21:15: warning: declaration of 'd' shadows a global declaration [-Wshadow]
 bool Try(int d)
               ^
towns.cpp:8:5: note: shadowed declaration is here
 int d[N][N],diam;
     ^
towns.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<work.size();i++)
              ~^~~~~~~~~~~~
towns.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<store.size();i++)
              ~~~^~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:70:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
  srand(time(0));
        ~~~~^~~
towns.cpp:68:29: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int _N, int sub)
                             ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 13 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 18 ms 512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 28 ms 512 KB Output is correct
3 Correct 17 ms 384 KB Output is correct
4 Correct 17 ms 512 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 384 KB Output is correct
2 Correct 18 ms 604 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 18 ms 512 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 17 ms 512 KB Output is correct
3 Correct 19 ms 512 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 17 ms 1024 KB Output is correct
3 Correct 18 ms 1060 KB Output is correct